《数据结构》实用试题及答案
1.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。（ C ）
A．688 B．678 C．692 D．696
2.二叉树的第k层的结点数最多为( D ).
A．2k-1 B.2K+1 C.2K-1 D. 2k-1
3.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼
树中总共有（ B ）个空指针域。
(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m
4.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历
该二叉树得到序列为（A ）。
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。
(A) 9 (B) 10 (C) 11 (D) 12
6.下面程序的时间复杂为（B ）
for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}
(A) O(n) (B) O(n2)
7.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针
的操作序列为（A ）。
(A) q=p->next；p->data=q->data；p->next=q->next；free(q)；
(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；
(C) q=p->next；p->next=q->next；free(q)；
(D) q=p->next；p->data=q->data；free(q)；
8.设二叉排序树中有n个结点，则在二叉排序树的平均平均查长度为（ B ）。
(A) O(1) (B) O(log2n) (C) (D) O(n2)
9.数据的物理结构主要包括___顺序存储结构__和__链式存储结构_____两种情况。
10.设一棵完全二叉树中有500个结点，则该二叉树的深度为____9______；若用二叉链表作为该完全二叉树的存储结构，则共有_____501______个空指针域。
11.设输入序列为1、2、3，则经过栈的作用后可以得到_____5______种不同的输出序列。
12.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为___i/2_______，右孩子结点的编号为____2i+1_______。
13.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为
（ C ）。
(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)
14．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点，最少有( C )个结点。
(A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1
15．在二叉排序树中插入一个结点的时间复杂度为（ B ）。
(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)
16.设用链表作为栈的存储结构则退栈操作（ B ）。
(A) 必须判别栈是否为满(B) 必须判别栈是否为空
(C) 判别栈元素的类型(D) 对栈不作任何判别
17.设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的
结点数为N2，则下列等式成立的是（ C ）。
(A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l
18.设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有___51__个空指针域。
二叉树的深度为k19.设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___n-i+1___个数据元素；删除第i个位置上的数据元素需要移动表中___n-i__个元素。
20.设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____BDCA________。
21.下图所示的森林：
(1) 求树（a）的先根序列和后根序列；
(2) 求森林先序序列和中序序列；
（3）将此森林转换为相应的二叉树；
A
B C
D E F
G
H
I J K
(a)(b)
答案：
(1)ABCDEF; BDEFCA；(2) ABCDEFGHIJK; BDEFCAIJKHG (3)森林转换为相应的二叉树；
A
G
B
C
D
E
F H
I
J
K
22.数据的最小单位是（ A ）。
(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量
23.函数substr(“DATASTRUCTURE”，5，9)的返回值为（ A ）。
(A) “STRUCTURE”(B) “DATA”
(C) “ASTRUCTUR” (D) “DATASTRUCTURE”
24.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍
然保持有序，则该操作的时间复杂度为（ D ）。
(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)
25.设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是
n，则输出序列中第i个输出元素是（ C ）。
(A) n-i (B) n-1-i (C) n+1-i (D) 不能确定
26.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。
答案：ABDECF，DBEAFC，DEBFCA
27.设一棵完全二叉树有128个结点，则该完全二叉树的深度为___8_____，有_____64_____个叶子结点。
28.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A ）。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
29.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件
是（ D ）。
(A) 空或只有一个结点(B) 高度等于其结点数
(C) 任一结点无左孩子(D) 任一结点无右孩子
30．顺序查不论在顺序线性表中还是在链式线性表中的时间复杂度为（ A ）。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
31.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的
队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ C ）。
(A) front->next=s；front=s； (B) s->next=rear；rear=s；
(C) rear->next=s；rear=s；(D) s->next=front；front=s；
32.设某哈夫曼树中有199个结点，则该哈夫曼树中有（ B ）个叶子结点。
(A) 99 (B) 100 (C) 101 (D) 102
33.设二叉排序树上有n个结点，则在二叉排序树上查结点的平均时间复杂度
为（ D ）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
34.for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为___0(n)______。
35.设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空
的条件为______F==R_______________。
36.（ B ）二叉排序树可以得到一个从小到大的有序序列。
(A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历
37.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则
编号为i结点的左孩子结点的编号为（ B ）。
(A) 2i+1 (B) 2i (C) i/2 (D) 2i-1
38.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ C ）。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
39.程序段s=i=0；do {i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（ A ）。
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)
40.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ C ）。
(A) 20 (B) 256 (C) 512 (D) 1024
41.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为
（ D ）。
(A) top=top+1; (B) top=top-1;
(C) top->next=top; (D) top=top->next;
42.哈夫曼树中没有度数为1的结点。
43.字符串的长度是指（C ）。
(A) 串中不同字符的个数(B) 串中不同字母的个数
(C) 串中所含字符的个数(D) 串中不同数字的个数
44.建立一个长度为n的有序单链表的时间复杂度为（ C ）
(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)
45.两个字符串相等的充要条件是（ C ）。
(A) 两个字符串的长度相等(B) 两个字符串中对应位置上的字符相等
(C) 同时具备(A)和(B)两个条件(D) 以上答案都不对
46.完全二叉树中第5层上最少有_______1___个结点，最多有_____16____个结点。
47.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在
结点A的后面插入结点X的操作序列为（ D ）。
(A) p->right=s；s->left=p；p->right->left=s；s->right=p->right；
(B) s->left=p；s->right=p->right；p->right=s；p->right->left=s；
(C) p->right=s；p->right->left=s；s->left=p；s->right=p->right；
(D) s->left=p；s->right=p->right；p->right->left=s；p->right=s；
48.设某棵完全二叉树中有100个结点，则该二叉树中有______50________个叶子结点。
49.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。
50.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ D ）
存储方式最节省运算时间。
(A) 单向链表(B) 单向循环链表
(C) 双向链表(D) 双向循环链表
51．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ B ）。
(A) s->next=p->next；p->next=-s；(B) q->next=s；
s->next=p；
(C) p->next=s->next；s->next=p；(D) p->next=s；
s->next=q；
52.二叉树第i(i≥1)层最多有（C ）个结点。
A．2i B．2i
C．2i-1D．2i -1
53.设单链表中指针p指向结点A，若删除A后的结点存在，则需要修改指针的操作为（A ）。
A．p->next=p->next->next B．p=p->next
C．p=p->next->next D．p->next=p
54.前序序列和中序序列相同的二叉树为没有左子树的二叉树;。
55.顺序存储的队列如果不采用循环方式，则会出现假溢出问题。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论