数据结构复习题1

1、 一. 填空题 1. 数据结构讨论的是数据及其相互之间的（）。 3 2 2 2. 一个算法中的语句频度之和为T（n） =（n n log2n - 18n）/n，则算法的时间复杂度 为 0（）。 3. 5阶对称矩阵中的数据元素以主对角线为中线对称，因此在存储时，可以将25个数据元 素压缩存储在（）个存储单元中。 4. 己知二维数组 A610（下标按C语言格式），每个数组元素占4个存储单元，若按行优 先顺序存放数据元素，a35的存储地址是1000,则a00的存储地址是（）。 5. 已知一棵树的边集合为, , , , , , , , ，贝U E的兄弟结点有（）个。 6. 对长度为13的有序表进行折半

2、查找，若该线性表的元素下标范围是0,12，则第一次查 找下标为（）的元素。 7. 一棵哈夫？树中有k个度为2的结点，则该树共含有（）个结点。 8. 对不？的关键字可能得到同？哈希地址，？ key1M key2，而f（key1）=f（key2）攌胙种现象称 为（ ） 9. 二叉排序树中，若左子树不空，则左子树上所有结点的关键字值均（）缈大于，等 于，小于）根？点的关键字值。 10. 斯特林公式从数量级上告诉我们，借助于“比较”进行排序的算法在最坏情况下能够达 到的最好的时间复杂度为0（）。 二. 选择题 1. 设使用某算法对n个元素进行处理，所需的时间是 法的渐进时间复杂度为（）。 A . O（

3、1）B. O（n） C. O（200n） 2 T(n)=(100n +200n+2000)/2n，则该算 D . O(nlog2n) 2. 3. 4. 非空的循环单链表first的尾结点（由p所指向）满足（）。 A. p-n ext = NULLB. p = NULLC. p-next = first D. p = first 设栈S和队列Q的初时状态皆为空，元素a1,a2,a3,a4,a5,a6依次通过一个栈，一个元素 出栈后即进入队列Q,若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1,则栈S至少应该容纳 （ A. 1 有一个 ）个元素。 B. 2 10阶对称矩阵 A, )。 C

4、. 3D.4 采用压缩存储方式（以行序为主序存储，且 A00=1 ),则 5. A85的地址是（ A. 36B. 37 一棵深度为4的完全二叉树，最少有（ A. 4B. 8C. 15 C. 42 D. 43 )个节点。 D. 6 A.顺序表B.循环链表C.双链表D.单链表 7. 使用下列序列构建二叉排序树，得到的最终结果与众不同的是（）。 A. 42135 B.42531 C.45213 D.45123 8. 均匀的散列函数应当使关键字集合中的元素，经散列函数映射到散列表中任何位置的概 率（ ）。 A .相等B .最小C.最大D. 定 9. 具有10顶点的无向图最多有（）条边。 A. 0B.

5、9C. 10D. 45 10. 对以下关键子序列用快速排序进行排序，情况（）速度最慢。 A. 19, 23, 3, 15, 7, 21,28B. 23, 21,28, 15, 19, 3, 7 C. 19, 7, 15, 28, 23, 21, 3D. 3, 7, 15, 19, 21,23, 28 三. 判断题 1. 线性链表的存取必须从头指针开始进行，头指针指示链表中第一个结点的存储位置。 2. 树的先根遍历和后根遍历可借用二叉树的先序遍历和后序遍历的算法实现之。 3. 空串的定义是由一个或多个空格组成的串。 4. 已知广义表 D=（A, B, C），贝U D的表尾运算 GetTail（D

6、） = （C）。 5. 后序遍历二叉排序树可得到一个关键字的有序序列。 四. 计算题 注意：请将题目的正确结果写在相应“答案”所示的位置处，写错或漏写均不得分。 1.使用普里姆（Prim）算法以0为源点，画出图1所示的无向图的最小代价生成树。 答案： 图1 2. 设S=A,B,C,D,E,F , W=2,3,5,7,9,12,对字符集合进行哈夫曼编码，W为各字符的频率。 试画出哈夫曼树。 3. 给定序列（47, 89, 44, 39, 70, 59, 103, 9, 67, 35）,建立一棵二叉排序树，画出 该树。 4. 试以关键字序列10, 20, 18, 15, 12,构造一棵平衡二叉树。

7、 5.已知结点A、B、C依次进栈，进栈后可立即出栈。问可以得到多少种不同的出栈序列? 试列举之。 五. 程序填空题 1.以下程序功能是：在带头结点的单链线性 表L中第i个位置之前插入兀素e。试补全该 程序。 Status Listlnsert_L(LinkList j = 0; while(p s = (LinkList)malloc(sizeof(LNode); s-data = e;(3); p-next = s; return OK; 答案：(1)。 (2)。 (3)。 2.以下程序功能是：先序遍历二叉树T的递 归算法，对每个数据元素调用函数Visit。其 中二叉树米用二叉链表存储结构，

8、Visit是对 数据元素操作的应用函数。试补全该程序。 Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e) if(T) Visit(T-data); if(T-lchild) PreOrderTraverse( (4), Visit); if(T-rchild) PreOrderTraverse( (5), Visit); 答案：(4)。 (5)。 六. 编程题 打印带头结点单链表L中的最大值。 该函数的函数函数声明：void Prin tMax(L in kList L); 单链表结构定义如下： typedef str

9、uct LNode ElemType data; struct LNode* next; LNode, *Li nkList; When you are old and grey and full of sleep, And no ddi ng by the fire, take dow n this book, And slowly read, and dream of the soft look Your eyes had once, and of their shadows deep; How many loved your mome nts of glad grace, And lov

10、ed your beauty with love false or true, But one man loved the pilgrim soul in you. And loved the sorrows of your cha nging face; And bending dow n beside the glow ing bars, Murmur, a little sadly, how love fled And paced upon the mountains overhead And hid his face amid a crowd of stars. The furthes

11、t dista nee in the world Is not betwee n life and death But whe n I sta nd in front of you Yet you dont know that I love you. The furthest dista nee in the world Is not whe n I sta nd in front of you Yet you cant see my love But whe n un doubtedly knowing the love from both Yet cannot be together. The furthest dista nee in the world Is not being apart while being in love But whe n I pla inly cannot resist the year ning Yet prete nding you have n ever bee