数据结构 选择题

88. 含5个结点（元素值均不相同）的二叉搜索树有（ ）种。 A、54 B、42 C、36 D、65

89. 对包含n个关键码的散列表进行检索，平均检索长度是（ ） A. O( log2n ) B. O( n ) C. O(n log2n ) D. 不直接依赖于n

90. 若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是:（ ）

A.快速排序 B.堆排序 C.归并排序 D.直接插入排序

91. 在最坏的情况下，查找成功时二叉排序树的平均查找长度（ ） A．小于顺序表的平均查找长度 B．大于顺序表的平均查找长度

C．与顺序表的平均查找长度相同 D．无法与顺序表的平均查找长度比较

92. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 （ ） A.n B.2n－1 C.2n D.n-1

93. 下述二叉树中，哪一种满足性质：从任一节点出发到根的路径上所经过的节点序列按其关键字有序 （ ）

A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆

94．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ） 。 A.HL = p; p->next = HL; B.p->next = HL; HL = p;

C.p->next = HL; p = HL; D.p->next = HL->next; HL->next = p;

95．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行 （ ）。

A.q->next = p->next ; p->next = q; B.p->next = q->next; q = p;

C.q->next = p->next; p->next = q; D.p->next = q->next ; q->next = p;

96．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 （ ）。 A.p = q->next ; p->next = q->next; B.p = q->next ; q->next = p;

C.p = q->next ; q->next = p->next; D.q->next = q->next->next; q->next = q;

97．栈的插入与删除操作在 进行（ ）。

A.栈顶 B.栈底 C.任意位置 D.指定位置

98．当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行 语句修改top指针（ ）。 A.top++ B.top-- C.top=0 D.top

99．若让元素1，2，3依次进栈，则出栈次序不可能出现 种情况（ ）。 A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，2

100．在一个循环顺序队列中，队首指针指向队首元素的（ ）位置。

9

A.前一个 B.后一个 C.当前 D.后面

101．当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为（ ） 。 A.N-2 B.N-1 C.N D.N+1

102．从一个循环顺序队列删除元素时，首先需要（ ） 。 A.前移一位队首指针 B、后移一位队首指针

C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素

103．假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是（ ） 。 A.f+1==r B.r+1==f C.f==0 D.f==r

104. 从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。 A.O(n) B.O(1) C.O(log2n) D.O(n2)

105.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（ ） A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构

106.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ） A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表

107.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（ ） A.4 B.5 C.6 D.7

108.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到（ ）

A.P=″SCIENCE″ B.P=″STUDY″ C.S=″SCIENCE″ D.S=″STUDY″

109.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为（ ） A.356 B.358 C.360 D.362

110.下列陈述中正确的是（ ）

A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分

111.n个顶点的有向完全图中含有向边的数目最多为（ ） A.n-1 B.n C.n(n-1)/2 D.n(n-1)

112.ALV树是一种平衡的二叉排序树，树中任一结点的（ ）

A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1

10

C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度

113. 在基于排序码比较的排序算法中，（ ）算法的最坏情况下的时间复杂度不高于O(nlog2n)。

A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序

114.如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。

A．起泡排序 B．快速排序 C．简单选择排序 D．堆排序

115.设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（ ）。

A．3700 B．4376 C．3900 D．4620

116. 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 A．3 B．2 C．1 D．1/2

117.向顺序栈中压入新元素时，应当（ ）。

A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行

118.线性链表不具有的特点是（ ）。

A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比

119.设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]中（ ）位置。 A．32 B．33 C．41 D．65

120、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ ）个。

A．n-1 B．n C．n+1 D．n+2

121.具有65个结点的完全二叉树的高度为（ ）。（设根的层次号为0） A．8 B．7 C．6 D．5

122.若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。 A．直接插入排序 B．快速排序 C．归并排序 D．直接选择排序

123.对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（ ）。

A．R[0]，R[1]，R[2]，R[3] B．R[0]，R[13]，R[2]，R[3] C．R[6]，R[2]，R[4]，R[3] D．R[6]，R[4]，R[2]，R[3]

11

124.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2)

125.带头结点的单链表first为空的判定条件是（ ）： A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL;

126.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。 A. n-2 B. n-1 C. n D. n+1

127.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ ），在被调用程序中可直接操纵实际参数。

A. 空间 B. 副本 C. 返回地址 D. 地址

128.在一棵树中，（ ）没有前驱结点。

A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点

129.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A. 2 B. 1 C. 0 D. -1

130.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9。

A. 20 B. 18 C. 25 D. 22

131.在有向图中每个顶点的度等于该顶点的（ ）。

A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差

132．下列说法正确的是（ ） A．数据是数据元素的基本单位

B．数据元素是数据项中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成

133．数据结构的基本任务是（ ）

A．逻辑结构和存储结构的设计 B．数据结构的运算实现 C．数据结构的评价与选择 D．数据结构的设计与实现

134．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）

A．O（1） B．O（n） C．O（nlog2n） D．O(n2)

135．顺序存储的线性表（a1,a2,?,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）

A．n B．n/2 C．n+1 D．(n+1)/2

12