《《数据结构》试题汇编》由会员分享，可在线阅读，更多相关《《数据结构》试题汇编（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构习题汇编一、单项选择题1. 在数据结构中，从逻辑上可以把数据结构分成（ ）。A. 动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2. 数据结构在计算机内存中的表示是指（ ）。A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系3. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A.逻辑B.存储C.逻辑和存储D.物理4. 计算机算法指的是（ ），它必须具备输入、输出和（ ）等 5 个特性A.计算方法B. 排序方法C.解决问题的有限运算序列D. 调度方法A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、
2、有穷性和稳定性D.易读性、稳定性和安全性5. 在一个长度为n的顺序表中向第i个元素（lWiWn+1）位置插入一个新元素时，需要从后向前依次后 移（ ）个元素。A. n-iB. n-i+1C. n-i-1D. i6. 在一个长度为n的顺序表中删除第i个元素（iWiWn）时，需要从前向后依次前移（）个元素。A. n-iB. n-i+1C. n-i-1D. i7. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）A. O（n）B. O（1）C. O（n2）D. O（log2n）8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。A. O（n）B. O（n/2）
3、C. 0（1）D. O（n2）9. 不带头结点的单链表 first 为空的判定条件是：（ ）A. first = NULL;B. first-next = NULL;C. first-next = first;D. first != NULL;10. 带头结点的单链表first为空的判定条件是：（）A. first = NULL;C. first-next = first;B. first-next = NULL;D. first != NULL;11.设单链表中结点的结构为（data, next）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s, 则应执行下列哪一个操作？（ ）A.
4、s-next = p; p-next = s;B. p-next = s; s-next = p;C. s-next = p-next; p = s;D. s-next = p-next; p-next = s;设单链表中结点的结构为（data, next）。若想摘除结点*p（*p既不是第一个也不是最后一个结点） 的直接后继，则应执行下列哪一个操作？（ ）A. p-next = p-next-next; B. p = p-next; p-next = p-next-next;C. p-next = p-next;D. p = p-next-next;非空的循环单链表first的尾结点（由p所指
5、向）满足：（）A. p-next = NULL;B. p = NULL;C. p-next = first;D. p = first;若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2D. 1, 3, 2当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。A. n-2B. n-1C. nD. n+1从一个顺序存储的循环队列中删除一个元素时，需要（ ）。A.队头指针加一B.队头指针减一C.取出队头指针所指的元素D.取出队尾指针所指的元素假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，贝0判断队
6、空的条件为（）。A. front+1 = rearB. rear+1 = frontC. front = 0D. front = rear树中所有结点的度等于所有结点数加（ ）。A.0B.1C.-1D.2在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A.2B.1C.0D.-1在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.nB.n-1C.n+1D.2*n在一棵具有n个结点的二叉树的第i层上（假定根结点为第1层，i大于等于1而小于等于树的高度）, 最多具有（ ）个结点。A. 2iB. 2i+1C. 2i-1D. 2n在一棵高度为h （假定根结点的层号为1）的完全二叉
7、树中，所含结点个数不小于（）。A. 2h-1B. 2h+1C. 2h-1D. 2h在一棵具有 35个结点的完全二叉树中，该树的高度为（）。假定空树的高度为0。12.13.14.15.16.17.18.19.20.21.22.23.24.A. 5B. 6C. 7D. 8在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。假定树根结点的编号为1。A. L（n-1）/2旦.|_n/2C.n/2|D. |_n/2-1在一棵完全二叉树中的编号为 1A. 2i在一棵完全二叉树中(A. L(i+1)/2)。若编号为 i 的结点存在左孩子，则左子女结点的编号为(B. 2i-1C. 2i+1D. 2i+
8、2)。假定根结点假定根结点的编号为1则对于编号为i (i1)的结点，其双亲结点的编号为B.L(i-1)/2_|C. Li/2D.Li/2-1设无向图的顶点个数为n,A. n-1B.则该图最多有n(n-1)/2C.)条边。n(n+1)/2D.n(n-1)n 个顶点的连通图至少有( )条边。A. n-1B. nC.n+1D.在一个无向图中，所有顶点的度数之和等于所有边数的 (A. 3B. 2C. 1)倍。D.1/2图的深度优先搜索类似于树的(A.先根B.中根图的广度优先搜索类似于树的(A. 先根B. 中根)次序遍历。C. 后根)次序遍历。C. 后根D. 层次D.层次n (n1) 个顶点的强连通图中
9、至少含有A. n-1B. n具有n个顶点的有向无环图最多可包含(A. n-1B. n一个有n个顶点和n条边的无向图一定是A. 连通的B. 不连通的)条有向边。C. n(n-1)/2D. n(n-1)C.C.在 n 个顶点的有向无环图的邻接矩阵中至少有(A. nB. n(n-1)/2C.)条有向边。n(n-1)/2D.n(n-1)。无环的D.有环的)个零元素。n(n+1)/2D.n(n-1)为了实现图的广度优先遍历， BFS 算法使用的一个辅助数据结构是(A.栈B.队列C.二叉树D.)。树若搜索每一个元素的概率相等，则在长度为 n( )。的顺序表上搜索到表中任一元素的平均搜索长度为A. nB.
10、n+1C.(n-1)/2D. (n+1)/2对长度为10的顺序表进行搜索(从表头开始搜索)，若搜索前面5个元素的概率相同，均为1/8，搜索 后面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为()。A. 5.5B. 5C. 39/8D. 19/425.26.27.28.29.30.31.32.33.34.35.36.37.38.39. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为()的值的向上取整。A. log2(n+1)B. log2nC. n/2D. (n+1)/240. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中
11、最大的为()的值的向下取整加一。A. log2 (n+1)B. log2nC. n/2D. (n+1)/241. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( ) 的值除以9。A. 20B. 18C. 25D. 2242. 对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为( )。A. 3B. 4C. 5D. 643. 对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为()。A. O(n)B. O(n2)C. O(1)D. O(log2n)44. 对 5 个不同的数据元素进行直接插入排序，最多需要进行( )次比较？
12、A. 8B. 10C. 15D. 2545. 如果输入序列是已经排好顺序的，则下列算法中( )算法最快结束？A.起泡排序B.直接插入排序C.直接选择排序D.快速排序46. 如果输入序列是已经排好顺序的，则下列算法中( )算法最慢结束？A.起泡排序B.直接插入排序C.直接选择排序D.快速排序二、填空题1. 算法的五个重要特性是有穷性、确定性、可行性、输入和输出。2. 设单链表中结点的结构为(data, next)。若想摘除结点*p本身，则应执行操作：q=p-next; p-data=q-data; p-next=q-next ; free(q);3. 设循环队列Q的队头和队尾指针分别为front
13、和rear,队列的最大容量为MaxSize，且规定判断队 空的条件为Q.front = Q.rear，则判断队满的条件为(Q.rear+1)%MaxSize=Q.front，而 计算队列长度的表达式为(Q.rear-Q.front+MaxSize)%MaxSize。4. 设有一个顺序栈S,元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3,s4, s6, s5, s1，则顺序栈的容量至少应为 3。5. 如果进栈序列是1, 2, 3, 4, 5, 6, 7, 8。则可能的出栈序列有_1430种。6. 用简单的模式匹配算法在主串aaaaaab中检索子串”aab”，贝总的比较次数为157.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.用简单的模式匹配算法在主串data_structure中检索子串string”，总的比较次数为 12。假定一棵三叉树(即度为3的树)的结点个数为50，贝怕的最小高度为5。假定根结点的高度为1。在一棵高度为3的四叉树中，最多含有21_结点。在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度 为0的结点数有丄个。一棵高度为5的完全二叉树中，最多包含有31个结点。假定根结点的
