精品文档
72． 以下数据结构中，哪一个是线性结构（ ）。
(A)广义表 (B)二叉树 (C)稀疏矩阵 (D) 串
73． 以下那一个术语与数据的存储结构无关？（ ）
(A)栈 (B)哈希表 (C)线索树 (D) 双向链表
74． 在下面的程序段中，对x的赋值语句的频度为（ ）。
FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;
(A) O(2n) (B)O(n) (C)O(n2) (D)O(log2n)
75． 以下哪个数据结构不是多型数据类型（ ）。
(A)栈 (B)广义表 (C)有向图 (D)字符串
76． 连续存储设计时，存储单元的地址（ ）。
(A)一定连续 (B)一定不连续
(C)不一定连续 (D)部分连续，部分不连续
77． 一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数
为（ A ）。
(A)0 (B)1 (C)2 (D)不确定
78． 设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（ B ）。
(A)O(n) (B)O(n+e) (C)O(n2) (D)O(n*e)
79． 下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（ A ）。
(A)堆排序 (B)冒泡排序 (C)快速排序 (D)SHELL排序
80． 已知数据表A中每个元素距其最终位置不远，则采用（ B ）排序算法最节省
时间。
(A)堆排序 (B)插入排序 (C)快速排序 (D)直接选择排序
81． 串是（ D ）。
(A)不少于一个字母的序列 (B)任意个字母的序列
(C)不少于一个字符的序列 (D)有限个字符的序列
82． 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（ A ）。
精品文档
精品文档
(A)23415 (B)54132 (C)31245 (D)14253
83． 设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个
数为（ D ）。
(A)r-f (B)r-f+1 (C)(r-f) mod n +1 (D)(r-f+n) mod n
84． 二叉树在线索化后，仍不能有效求解的问题是（ D ）。
(A)先序线索二叉树中求先序后继 (B)中序线索二叉树中求中序后继
(C)中序线索二叉树中求中序前驱 (D)后序线索二叉树中求后序后继
85． 求最短路径的FLOYD算法的时间复杂度为（ D ）。
(A)O(n) (B)O(n+e) (C)O(n2) (D)O(n3)
86． 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（ B ）。
(A)0 (B)1 (C)2 (D)不确定
87． 数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为
1000的连续的内存单元中，则元素A[5,5]的地址为（ A ）。
(A)1140 (B)1145 (C)1120 (D)1125
88． 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是
（ A ）。
(A)快速排序 (B)希尔排序 (C)冒泡排序 (D)堆排序
89． 对有18个元素的有序表做折半查找，则查找A[3]的比较序列的下标依次为
（ D ）。
(A)1-2-3 (B)9-5-2-3 (C)9-5-3 (D)9-4-2-3
90． 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是
（ D ）。
(A)堆排序 (B)冒泡排序 (C)快速排序 (D)直接插入排序
91． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已
知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（ B ）型调整以使其平衡。
(A)LL (B)LR (C)RL (D)RR
92． 下列各式中，按增长率由小至大的顺序正确排列的是（ ）。
(A)n,n!,2n,n3/2 (B)n3/2,2n,nlogn,2100 (C)2n, logn, nlogn, n3/2 (D)2100, logn, 2n, nn 精品文档
精品文档
93． 若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（ ）。
(A)s-＞next=p-＞next; p-＞next=s;
(B)p-＞next=s; s-＞next=p-＞next (C)p-＞next=s-＞next; s-＞next=p; (D)s-＞next=p;p-＞next=s-＞next;
94． 若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环
链表各设置一个指针，分别指向（ ）。
(A)各自的头结点 (B)各自的尾结点
(C)各自的第一个元素结点 (D)一个表的头结点，另一个表的尾结点
95． 栈的两种常用存储结构分别为（ ）。
(A)顺序存储结构和链式存储结构 (B)顺序存储结构和散列存储结构
(C)链式存储结构和索引存储结构 (D)链式存储结构和散列存储结构
96． 已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值
分别为8和3，则该队的当前长度为（ ）。
(A)5 (B)6 (C)16 (D)17
97． 已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该
链串的存储密度为（ ）。 typedef struct node{ char date[8];
struct node * next; } LinkStrNode;
(A)1/4 (B)1/2 (C)2/3 (D)3/4
98． 应用简单的匹配算法对主串s=“BDBABDABDAB”与子串t=“BDA”进行模
式匹配，在匹配成功时，进行的字符比较总次数为（ ）。
(A)7 (B)9 (C)10 (D)12
99． 二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且
第1个元素的首地址为200，则元素A[8][9]的存储地址为（ ）。 (A)574 (B)576 (C)578 (D)580
100． 对广义表L=((a,b),c,d)进行操作tail (head (L))的结果是（ ）。
(A)(c,d ) (B)(d ) (C)b (D)(b)
101． 已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行
层次遍历得到的序列为（ ）。
(A)ABCDEF (B)ABCEFD (C)ABFCDE (D)ABCDFE 精品文档
精品文档
102． 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算
该有向图中某个顶点出度的时间复杂度为（ ）。
(A)O(n) (B)O(e) (C)O(n+e) (D)O(n2)
103． 在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键
字为45，89和12的结点时，所需进行的比较次数分别为（ ）。 (A)4，4，3 (B)4， 3， 3 (C)3，4，4 (D)3，3，4
104． 下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（ ）。
(A)冒泡排序 (B)直接选择排序 (C)堆排序 (D)归并排序
105． 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概
率情况下查找成功的平均查找长度等于（ ）。
(A)1.0 (B)2.9 (C)3.4 (D)5.5
106． 在下列各种文件中，不能进行顺序查找的文件是（ ）。
(A)顺序文件 (B)索引文件 (C)散列文件 (D)多重表文件
107． 下面带有@标记的语句的频度(n>10)是（ ）。
for(int i=0;i for(int j=i+1;j (A)n*(n-1)/2 (B)n*n/2 (C) n*(n+1)/2 (D)不确定 108． 已知使用顺序表存储数据，表长为n，假设在表中的任意位置插入元素的 概率相等，则插入一个元素，平均需要移动的元素个数（ ）。 (A)(n-1)/2 (B)n/2 (C)(n+1)/2 (D)不确定 109． 在双向链表p所指结点之后插入s所指结点的操作是（ ）。 (A)p?right=s;s?left=p;p?right?left=s;s?right=p?right; (B)p?right=s;p?right?left=s;s?left=p;s?right=p?right; (C)s?left=p;s?right=p?right;p?right=s;p?right?left=s; (D)s?left=p;s?right=p?right;p?right?left=s;p?right=s; 110． 字符串相等的充分必要条件是（ ）。 (A)串长度相等 (B)串使用相同的存储结构 (C)串相同位置对应的字符相等 (D)A和C 111． 将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。 (A) 数组 (B) 栈 (C) 队列 (D)二叉树 精品文档 精品文档 112． 一个栈的入栈序列1, 2, 3, 4, 5, 则栈的不可能的输出序列是（ ）。 (A) 12345 (B)54321 (C)32514 (D)12354 113． 设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素 个数为（ ）。 (A)r-f (B)r-f+1 (C)(r-f) mod n +1 (D)(r-f+n) mod n 114． 某二叉树的前序遍历结点访问顺序是ABDEFCGH, 中序遍历的结点访问 顺序是DBFEAGHC, 则其后序遍历的结点访问顺序是（ ）。 (A) DFEBHCGA (B)DFEBHGCA (C)DEFBHGCA (D)DFEHBGCA 115． 正则二叉树是只有度为0和2的结点的二叉树，已知正则二叉树的叶子结 点个数为n，则该二叉树总得结点数为（ ）。 (A) n+1 (B)2*n (C) 2*n+1 (D)2*n-1 116． 下面关于排序的说法错误的是（ ）。 (A)快速排序、归并排序都是一种不稳定的排序方法 (B)直接插入排序和折半插入排序移动元素的次数相同 (C)简单选择排序移动元素的次数最少 (D)根据排序需要的平均时间，快速排序是目前最好的一种内部排序方法 117． 折半查找有序表（3，4，5，10，13，14，20，30），若查找元素3， 则 被比较的元素依次为（ ）。 (A)10,20,30 (B)10,14,30 (C)13,3 (D)10, 4, 3 118． 下面关于栈和队列的说法正确的是（ ）。 (A)栈是先进先出的线性表，队列是后进先出的线性表 (B)栈是先进先出的线性表，队列也是先进先出的线性表 (C)栈是后进先出的线性表，队列是先进先出的线性表 (D)栈是后进先出的线性表，队列也是后进先出的线性表 119． 两个各有n个元素的有序列表并成一个有序表，其最少的比较次数是 （ ）。 (A)n (B)2n-1 (C)2n (D)n-1 120． 设循环队列中数组的下标范围是0~ n-1，f表示队首元素的前驱位置，r表 示队尾元素的位置，则队列中元素个数为（ ）。 (A)r-f (B)r-f 1 (C)(r-f 1)mod n (D)(r-f n)mod n 精品文档
最新数据结构试题库
