资源描述：
《东华理工大学数据结构A卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、选择题（每空2分，共20分）1、设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(n2)C.O(n)D.O(n3)2、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（C）存储方式最节省运算时间。(A)双链表(B)单链表(C)顺序表(D)单循环链表3、若长度为n的线性表采用顺序存储结构，在其第i（1≤i≤n+1）。个位置插入一个新元素的算法的时间复杂度为（C）
2、A．O(0)B．O(1)C．O(n)D．O(n2)4、若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是n，则第i个输出元素是（D）A.不确定B.n-iC.n-i-1D.n-i+15、设有广义表D=（a，b，D），其长度为（C）A.1B.2C.3D.无穷6、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（C）A．4B．5C．6D．77、在有n个叶子节点的哈夫曼树中，其节点总数为（D）A、不确定B、2nC、2n+1D、2n-18、要联通一个具有n个顶点的无向图
3、中，要连通全部顶点至少需要(A)条边。A.n-1B.nC.n+1D.2n9、在一个具有ｎ个顶点和ｅ条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（D） Ａ．ｎ Ｂ．ｎ×ｅ Ｃ．ｅ Ｄ．２×ｅ10、下列排序方法中，哪一个是稳定的排序方法？（A）A．直接插入排序B．希尔排序C．堆排序D．快速排序二、填空题（每空2分，共20分）1、线性表是一种线性结构,一个线性表中的所有元素应与结点之间存在一对一的关系2、一个顺序表的第一个元素的存储地址是2000
4、，若每个元素的所占存储空间长度为5，则第8个元素的存储地址是20353、在表长为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，插入的新元素作为第i个元素，则涉及到的元素的移动次数为n-i+14、对于一单链表L（L为头指针，且结点的后继指针分量为next），其p结点（p为链表中某结点的指针）既不是第一个结点，也不是最后一个结点，在p结点后插入s结点（s为某结点的指针）的语句序列是s->next=p->next;p->next=s;5、设有广义表D=（（a，b），（c，d））则Head（D）=（a，b
5、）Tail（D）=（c，d）6、设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为F==R。7、设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有m=2e关系。8、设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是(12，18，24，27，35，26)。9、设一个连通图G中有n个顶点e条边，则其最小生成树上有n-1条边。三、应用题（40分）1.已知一个6行*7列的稀疏矩阵A如图所示，试写出它的三元组线性表。0400000
6、000-3001800000000050000-7000200006000解：((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6))2.已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA，请画出该二叉树，并给出先序序列。（5分）解：二叉树：A/BC/\DEF/\/GHIJKL先序序列：ABDGLHEICFJK3.已知如图所示的有向图，请给出该图的：（1）每个顶点的入出度；（2分）
7、（2）邻接表；（4分）解：（1）（2）顶点123456入度321122出度0223134.某图的邻接矩阵如图，画出从顶点1出发的深度优先生成树。（6分）01111011001001100010011001101011010000110111000105.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}
8、;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。（6分）解：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)206.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。（6分）解：先将概率放大100倍，以方便构造哈夫曼树。w={7,19
