复习题1

7 有7个带权结点，其权值分别为4，7，8，2，5，16，30，以它们为叶子结点构造一颗哈夫曼树（要求按每个结点的左子树根结点的权值小于或等于右子树根结点的权值的次序构造），并计算出其带权路径长度WPL。

可得带权路径长度：

WPL=(2+4)×5+(5+7+8)×4+16×2+30×1=172

1、一个n个顶点的无向图最多有 条边。 (A)n (B)n(n-1) (C)n(n-1)/2 (D)2n 2、

（A）1/2 （B）1 （C）2 （D）4 3.两种遍历算法。

1、设线性表（a1，a2，…，a500）元素的值由小到大排列，对一个给定的k值用折半法查找线性表，在查找不成功的情况下至多需比较 次

1. ?log2n?+1

2 试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求。对长度为n的表来说，三种查找法在查找成功时的查找长度各是多少？

查找要求:顺序查找法：表中元素可以任意存放,(n+1)/2 折半查找法：有序存放 log2(n+1)-1

分块查找法：分块有序(n/s+s)/2+1,b为块数，s为块中记录数

1.数据的基本单位是（ C ）

A.数据项 B.数据类型 C.数据元素 D.数据变量 2.下列程序的时间复杂度为（ C ） i=0；s=0； while（s

{ i++； s=s+i； }

A.O（ ） B.O（ ） C.O（n） D.O（n2）

3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ D ） A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表

4.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（ A ）

A.n-i B.n-i+1 C.n-i-1 D.i

5.顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（C ）

A.s.elem［top］=e； B.s.elem［top+1］=e； s.top=s.top+1； s.top=s.top+1； C.s.top=s.top+1； D.s.top=s.top+1； s.elem［top+1］=e； s.elem［top］=e；

6.循环队列sq中，用数组elem［0??25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（ D ） A.8 B.16 C.17 D.18

8.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（A ） A.3 B.4 C.5 D.6

10.有n个结点的有向完全图的弧数是（ C ） A.n2 B.2n C.n(n-1) D.2n(n+1)

11.设图的邻接链表如题12图所示，则该图的边的数目是（B ）

A.4 B.5 C.10 D.20

12.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（ B ） A.1 B.2 C.3 D.4

13.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）

A.选择排序 B.快速排序 C.冒泡排序 D.插入排序

14．数据结构是（ D ） A．一种数据类型 B．数据的存储结构

C．一组性质相同的数据元素的集合

D．相互之间存在一种或多种特定关系的数据元素的集合 15．算法分析的目的是（ B ） A．辨别数据结构的合理性 B．评价算法的效率

C．研究算法中输入与输出的关系 D．鉴别算法的可读性

16．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ D ） A．插入 B．删除 C．排序 D．定位

17．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ B ）

A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1

18．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ A ） A．1207 B．1209 C．1211 D．1213

19．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ A ） A．队列 B．栈

C．线性表 D．有序表

20．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（B ）

A．不一定相同 B．都相同 C．都不相同 D．互为逆序

1．称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和___ f(n)____的数量级相同。

2．假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为_10___。

3．一棵含999个结点的完全二叉树的深度为_______。 4．含n个顶点的无向连通图中至少含有______条边。

6．在数据结构中，数据的逻辑结构分为集合、________、树形结构和图状结构等四类。

7. 顺序表的存储密度为________，而链表的存储密度为________。 是指一个结点中数据域所占的存储单元和整个结点所占的存储单元之比

8. 对于栈只能在________插入和删除元素。

9. 在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为________。

10. 三个结点可构成________种不同形态的二叉树。

1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度： (1)查找不成功，即表中无关键字等于给定值K的记录； (2)查找成功，即表中有关键字等于给定值K的记录。

答：查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。