数据结构复习题(4A)

} }

}

3.欲向线性表L的表头插入元素X，完成下面程序段中的部分语句：

void InsertFirstList( struct List *L,ElemType X) {

int i; if(_L->size==L->MaxSize) againMalloc(L); for(i=L->size-1;i>=0;i--) L->list[i+1]=L->list[i]; L->list[0]=X; L->size++; }

第3章 稀疏矩阵和广义表

一、单选题（共有题目4题）

1.设一个具有t个非零元素的m×n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为（ ）。

A. O(m) B. O(n) C. O(n+t) D. O(n×t) 标准答案：D

2.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）。

A. 行号 B. 列号 C. 元素值 D. 地址 标准答案：A

3.广义表( )的表头是( )。

A. ( ) B. 没有表头 C. (( )) D. 0 标准答案：B

4.广义表( )的表尾是( )。

A. 没有表尾 B. ( ) C. ( ( ) ) D. 0 标准答案：A

二、填空题（共有题目16题）

1.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的行号、列号和元素值3项。 2.(( ),(e),(a,(b,c,d)))的表头是() 或 空表。

3.一个广义表中的元素分为单（原子）元素和表（子表）元素两类。

4.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为值域和子表指针域。 5.一个广义表的深度等于括号嵌套的最大层次数。

6.稀疏矩阵是一种非零元素的个数远远小于零元素的个数，且非零元素的分布没有规律的矩阵。 7.广义表(( ))的表头是( ) 或 空表。

8.在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应大于对应三元组线性表的长度。

9.广义表((e),(a,(b,c,d)))的深度是3。 10.广义表( ( ) )的表尾是( ) 或 空表。

11.(( ),(e),(a,(b,c,d)))的表尾是((e),(a,(b,c,d)))。

12.在一个广义表的存储结构中，每个结点均包含有_3个域。 13.广义表((e),(a,(b,c,d)))的长度是2。

14.在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有4个域，在相应的十字链接存储中，每个结

9

点包含有5个域。

15.在稀疏矩阵的十字链接存储中，每个结点的down指针域指向列号相同的下一个结点，right指针域指向行号相同的下一个结点。

16.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按行号为主序列号为辅序的次序排列。 三、判断题（共有题目1题）

1.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。对

第4章 栈和队列

一、单选题（共有题目9题）

1.在一个顺序队列中，队首指针指向队首元素的（ ）位置。

A. 前一个 B. 后一个 C. 当前 D. 后面 标准答案：A

2.假定利用数组a[N]循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未空，当进行出队并返回队首元素时所执行的操作为( )。

A. return a[++r%N]; B. return a[--r%N]; C. return a[++f%N]; D. return a[f++%N]; 标准答案：C

3.一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为（ ）。

A. top->next=top; B. top=top->data;

C. top=top->next; D. top->next=top->next->next; 标准答案：C

4.一个链栈的栈顶指针用top表示，当p所指向的结点进栈时，执行的操作为（ ）。

A. p->next =top; top=top->next; B. top=p; p->next=top; C. p->next=top->next;top->next=p; D. p->next=top;top=p; 标准答案：D

5.栈的插入和删除操作在（ ）进行。

A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 标准答案：A

6.当利用大小为N的数组顺序存储一个队列时，若没设有队列长度的变量，则该队列的最大长度为（ ）。

A. N-2 B. N-1 C. N D. N+1 标准答案：B

7.若让元素1、2、3依次进栈，则出栈次序不可能出现（ ）情况。

A. 3，2，1 B. 2，1，3 C. 3，1，2 D. 1，3，2 标准答案：C

8.从一个顺序队列删除元素时，首先需要（ ）。

A. 队首指针循环加1 B. 队首指针循环减1

C. 取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 标准答案：A

9.假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为( )。

A. front==rear B. front!=NULL C. rear!=NULL D. front==NULL 标准答案：D

二、填空题（共有题目7题）

1.后缀表达式“4 5 * 3 2 + -”的值为15。 2.栈又称为后进先出表，队列又称为先进先出_表。 3.队列的插入操作在队尾进行，删除操作在队首进行。

4.中缀表达式3*(x+2)-5所对应的后缀表达式为3 x 2 + * 5 -。

5.在一个链队中，若队首指针与队尾指针的值相同，则表示该队为空或该队只含有一个结点。

10

6.在一个不设队列长度变量的顺序队列Q中，判断队空的条件为Q.front==Q.rear，判断队满的条件为(Q.rear+1)% Q.MaxSize==Q.front。

7.向一个栈顶指针为HS的链栈中插入一个新结点*p时，应执行p->next=HS和HS=p操作。

第5章 树和二叉树

一、单选题（共有题目17题）

1.在一棵完全二叉树中，若编号为i 的结点存在左孩子，则左孩子结点的编号为（ ）。

A. 2i B. 2i-1 C. 2i+1 D. 2i+2 标准答案：A

2.在一棵树中，每个结点最多有（ ）个前驱结点。

A. 0 B. 1 C. 2 D. 任意多个 标准答案：B

3.在一棵具有n个结点的二叉树的第i层上，最多具有（ ）个结点。

A. 2 i B. 2 i-1 C. 2 i-1 D. 2 n 标准答案：C

4.在一棵具有35个结点的完全二叉树中，该树的深度为（ ）。 A. 6 B. 7 C. 5 D. 8 标准答案：A

5.在一棵具有n个结点的完全二叉树中，树枝结点的最大编号是（ ）。

A. (n+1)/2 B. (n-1)/2 C. n/2-1 D. n/2 标准答案：D

6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。

A. 2 B. 1 C. 0 D. -1 标准答案：A

7.在一棵完全二叉树中，对于编号为i(i>1)的结点，其双亲结点的编号为（ ）。

A. (i+1)/2 B. (i-1)/2 C. i/2 -1 D. i/2 标准答案：B、D

8.一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f))，则该二叉树的高度为（ ）。

A. 3 B. 4 C. 5 D. 6 标准答案：C

9.一棵树的广义表表示为a(b(c),d(e,f(g(h,i))),j)，该树的深度为（ ）。

A. 3 B. 4 C. 5 D. 6 标准答案：C

10.在一棵深度为h的完全二叉树中，所含结点个数不大于（ ）。

A. 2 h B. 2 h+1 C. 2 h -1 D. 2 h-1 标准答案：C

11.树中所有结点的度等于所有结点数加（ ）。

A. 0 B. 1 C. －1 D. 2 标准答案：C

12.一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f))，则该二叉树所含的单分支结点数为（ ）。A. 2 B. 3 C. 4 D. 5 标准答案：B

13.在一棵完全二叉树中，若编号为i（1≤i≤n）的结点存在右孩子，则右孩子结点的编号为（ A. 2i B. 2i-1 C. 2i+1 D. 2i+2 标准答案：C

14.在一棵深度为h的完全二叉树中，所含结点个数不小于（ ）。

A. 2 h B. 2 h+1 C. 2 h -1 D. 2 h-1

。

11

）标准答案：D

15.对于一棵具有30个结点的三叉树，则其最小深度为（ ）。

A. 3 B. 4 C. 5 D. 6 标准答案：B

16.对于一棵深度为4的三叉树，最多具有（ ）个结点。

A. 30 B. 36 C. 40 D. 54 标准答案：C

17.在一棵二叉树中，叶子结点数等于双分支结点数加（ ）。

A. 0 B. 1 C. －1 D. 2 标准答案：B

二、填空题（共有题目12题）

1.对于一棵具有n个结点的树，则树中所有结点的度数之和为n-1。 2.对于一棵含有40个结点的理想平衡树，它的高度为6_。 3.在一棵二叉树中，第5层上的结点数最多有16个。 4.一棵高度为3的四叉树中，最多含有21_结点。

5.在一棵二叉树中，若双分支结点数为5个，单分支结点数为6个，则叶子结点数为6个。 6.一棵三叉树的结点个数为50，则它的最小深度为5，最大深度为50。

7.在一棵高度为5的理想平衡树中，最少含有16个结点，最多含有31个结点。

8.一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则结点H的双亲结点是B，孩子结点有I、J。 9.一棵二叉树顺序存储在一维数组a中，则a[i]（1≤i≤n）元素的左孩子元素为a[2i]，右孩子元素为a[2i+1]。 10.已知一棵二叉树的先根和中根序列如下：先根序列：A，B，C，D，E，F，G，H，I，J中根序列：C，B，A，E，F，D，I，H，J，G则其后根序列为C B F E I J H G D A。

11.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数有2个，则度为0的结点数有6个。

12.一棵深度为5的满二叉树中的结点数为31个。

第6章 二叉树的应用 一、单选题（共有题目10题）

1.对二叉搜索树进行中序遍历得到的结点序列一定是一个有序序列。对 2.利用n个值作为叶子结点的权生成的哈夫曼树中共包含（ ）结点。

A. n B. n+1 C. 2n D. 2n-1 标准答案：D

3.有四个带权叶子结点，其权值分别为2、4、5、9，则由其构成的哈夫曼树的带权路径长度是（ ）。

A. 50 B. 40 C. 37 D. 20 标准答案：C

4.向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。

A. O（1） B. O（Log2n) C. O(n) D. O(nLog2n) 标准答案：B

5.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n) B. O(1) C. O(Log2n) D. O(n2) 标准答案：C

6.根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为（ ）。

A. O（n) B. O(Log2n) C. O(n2) D. O(nLog2n) 标准答案：D

7.利用n个值作为叶子结点的权生成的哈夫曼树中共包含（ ）个双分支结点。

A. n B. n-1 C. n+1 D. 2n-1 标准答案：B

12