绵阳数据结构

1、一、 单项选择题（本大题共20小题，每小题1分，共20分）请将正确选项前的字母填在题后的括号内。1. 在顺序存储的线性表(a1,a2,.,an)中,删除任意一个结点时所需移动结点的平均次数为（）。 A、n B、n/2 C、(n-1)/2 D、(n+1)/22.下列算法suanfa2的时间复杂度为_。int suanfa2(int n) int t=1； while(t<=n) t=t*2；return t； A.O(log2n) B.O(n) C.O(n2) D.O(2n) 3._又称为FIFO表。A.队列 B.栈 C.散列表 D.哈希表 4.若6行8列的数组以列序为主序顺序存储,基地址

2、为1000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是_。 A.1086 B.1068 C.1032 D.答案A,B,C都不对5.广义表(a,(b,( ),c),(d,(e)的深度是_。 A.2 B.3 C.4 D.56. 若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（）。 A、归并排序 B、快速排序 C、直接选择排序 D、直接插入排序7.与中缀表达式a+b*c-d等价的前缀表达式是_。 A.+a-*bcd B.*+-abcd C.-+a*bcd D.abcd+*- 8.折半查找有序表(6,15,30,37,65,

3、68,70,72,89,99),若查找元素37,需依次与表中元素_进行比较,。 A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,379.对长度为10的表作选择(简单选择)排序,共需比较_次关键字。 A.45 B.55 C.90 D.11010.对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为_。 A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n )11.一组记录的关键字经一趟二路归并排序后得到含有5个长度为2的有序表如下：25，48，16，35，79，82，23，40，36，72，在此基础上按二路归并排序方法再对该

4、序列进行一趟归并后的结果为（）。 A、16，25，35，48，79，82，23，36，40，72 B、16，25，35，48，23，40，79，82，36，72 C、16，25，48，35，79，82，23，36，40，72 D、16，25，35，48，79，23，36，40，72，8212.将线性表的数据元素以_结构存放, 查找一个数据元素所需的时间不依赖于表的长度。A.循环双链表 B单链表 C.哈希(Hash)表 C.一维数组 13.设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有_。 A.a.b,c,d B.a,d,b,c C.b,a,d,c D.c,d,a,b14.

5、 _ 又是一棵满二叉树。 A.深度为5有31个结点的二叉树 B.有15个结点的完全二叉树C.哈夫曼(Huffman)树 D.二叉排序树15.查找哈希(Hash)表,解决冲突的的方法有_B_。 A.除留余数法 B.线性探测再散列法 C.直接地址法 D.链地址法16.算法指的是（ c ） A计算机程序 B解决问题的计算方法 C解决问题的有限运算序列 D排序算法 17.由_D_组成的集合是一个数据对象。 A.不同类型的数据项 B.不同类型的数据元素 C.相同类型的数据项 D.相同类型的数据元素18、在一个单链表HL中，若要向q所指结点之后插入一个由指针p指向的结点，则执行  （D

6、）      A、HL=p;p->next=HL     B、p->next=HL;HL=pC、P->next=q->next;q->next=p  D、p->next=q->next;q=p>next19、由权值分别为3，8，10，2，6的叶子结点生成一棵哈夫曼树，该树中双分支结点数为 A、2  B、3  C、4     D、520 设sub(s,i,j)的功能是返回串s从第i

7、个字符开始长度为j的子串，scopy(s,t)的功能是复制串t到s，若字符串s=SCIENCESTUDY，则调用scopy(p,sub(s,1,7)后得到( A)A、p=SCIENCEB、p=STUDY C、s=SCIENCED、s=STUDY17.下图是一个AOV网，（B）是它的拓扑序列。ABCDEA.ABCDE B.ACDBE C.ADBCE D.CADBE 18.对一个算法的评价，不包括如下（D ）方面的内容。A.可读性 B.正确性 C.时间复杂度 D.并行性19.递归算法必须使用（A）。A.线性表 B.图 C.栈 D.队列20.当稀疏矩阵采用十字链表的链式存储时，它的包括元素的行号、列

8、号、元素本身的信息和（D）的指针域。A.指向同一行中下一个有效节点的指针B.指向同一列中下一个有效节点的指针C.分别指向所在行和列的的下一个有效节点的指针D.指向头节点的指针二、填空题（本大题共10小题，每小题2分，共12分）不写解答过程，将正确的答案写在每小题的空格内。1. 在串S=“structure”中，以t为首字符的子串有     2  个。2. 查找表分为静态查找表和动态查找表两种，二叉排序树属于  动态树表    。3. .第i趟在n-i+l (i=1，2，n-l)个记录中

9、选取键值最小的记录作为有序序列的第i个记录。这样的排序方法称为  选择排序 。4. 对某非空二叉树进行前序、中序遍历时，所得的结果完全相同（即结点序列一致），则这棵二叉树必定是 完全二叉树5. 一个数据结构在计算机中的表示(映象)称为 数据的物理结构6. .线性表中 _元素的个数 称为表的长度。7. 从二叉排序树种查找一个元素的时间复杂度是O（log2N）_。8. 如果一个数据结构的元素个数为n，n>=0，则该数据结构不可能是_空表_。9. 一个二叉树可以还原为一棵树的条件是该二叉树_中序上将左右子树分开。10. 有一个5维矩阵的元素k，则k最多有_24_个后继。1. 当线性表

10、经常需要查找表中的数据时，应该采用_顺序_存储结构。2. 一个栈的输入顺序为123，则栈的可能输出序列有_321_。3. 队列的插入是在_队尾部_，在_队头_删除，因此队列又称为_先进后出_。4. 一棵二叉树有30个节点，其中叶节点有10个，则度为2的节点有_9_个，度为1的节点有_6_个。5. 一棵二叉树有n个节点，则有_1_指针域被浪费了，所以我们通常用这些没有使用的指针域指向该节点的前驱或者后继，称之为_线索二叉_树。6. 如果串采用动态的顺序存储，我们称为_堆存储_。在循环队列中，为了正确判定队满和队空，常常留一个空间不存储数据，则队满的条件是_（Q.rear+1）%MAXQSIZE=

11、Q.front_，队空的条件是_Q.front=Q.rear_。7. 在线性表的散列存储中，处理冲突的常用方法有_线性探测再散列、二次探测再散列_和_两种。8. 有一个8阶上三角矩阵（行列序号从0开始编号），采用行优先顺序存储为一个顺序表，如果第一个元素的起始地址为L(0)，每个元素需要4个字节，则任意数组元素ai,j的存储开始地址是_。11. 对某非空二叉树进行前序、中序遍历时，所得的结果完全相同（即结点序列一致），则这棵二叉树必定是_完全二叉树_12. 一个数据结构在计算机中的表示(映象)称为 _数据的物理结构_。队列是一种先进先出的数据结构，具有出队和入队两种基本操作，如果采用顺序存储，

12、循环队列的出队操作是_p->front= (p->front+1) % MAXLEN13. _（队头：front，队列的最大元素个数为m）。14. 和队列相反，栈是一种具有_先进后出_特点的数据结构。15. 已知单链表每个节点的结构为：struct nodeint data;node *next;，想在p节点后插入e元素的操作为：struct node q;q=(struct node *)malloc(sizeof(struct node);q->data=e;q->next=_q->data_;p->next=_q->

13、next_; 16. 堆存储是指_动态分配的空间都在堆上_。17. 广义表的表头可以是广义表或者独立元素，表尾则一定是 第一个元素去掉剩余的部分_。18. 排序是指 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。抽象数据类型定义包括三部分：数据对象、数据关系和基本操作19. 字符串是指_由数字、字母、下划线组成的一串字符，模式匹配是指_数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串_。1. 广义表A=(a)，(),()的表尾是_(a)，(),()_，深度是_3_。2. 有一个顺序表，

14、数据元素的定义为：struct datachar name10;int num;data;如果第一个元素的起始地址为L(0)，每个元素需要_个字节的存储空间，则任意第i个元素的存储首地址是_。3. 数据的物理存储结构主要包括顺序和_链式存储_两种情况。4. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_7_次就可以断定数据元素X是否在查找表中。已知P节点是某双向量表的中间节点，在P节点后插入S节点的语句序列是：_ s->next=p->next; p->next=s;5. _三、判断下列叙述是否正确(本大题共5小题，每小题1分，共5分)1字符串

15、的长度是指串中不同字符的个数。对2 存在这样的二叉树，对它采用任何次序遍历结果都相同。对3 在堆排序中，一个堆的堆根元素一定是一个最小数或最大数 对4 完全二叉树中，若某个结点没有左孩子，则该结点一定是叶子结点。对5 线性表的逻辑顺序与存储顺序总是一致的。错四、试画出下列存储结构图(每小题5分,共15分)1.数组A1.2,0.2 的以列序为主序的顺序存储结构。2.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。3.二叉树的顺序存储结构:1.广义表L=（a,b,(c)）的链式存储。3、如下稀疏矩阵的三元组存储结构。1.画出数组A0.2,0.2的以列序为

16、主序的顺序存储结构图，起始地址为loc，每个元素占有4个字节。2.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈，指明栈顶和栈底。4.已知图G中的边为<a,b>,<a,f>,<c,d>,<e,a>,<b,c>，画出该图五、解答题 (每小题6分,共24分)1. 设电文中出现字字母A、B、C、D、E、F、G、H每个字母在电文中出现的次数分别是5，25，4，7，9，12，30，8，请画出哈夫曼树，求A,B,C,D的哈夫曼编码及哈夫曼树的WPL。2.试按表( 10,8,9,12,20,5,6,15,

17、19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。 (1)试画出插入完成之后的二叉排序树； (2)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。3.1 (3)对该树进行中序遍历,试写出中序遍历序列。中：5,6,8,9,10,12,15,19,20,253.试将森林 F= T1,T2,T3,T4 转换为一棵二叉树。 T1 T2 T3 T44.已知一棵二叉树的前序遍历序列和中序遍历序列分别是： I,A,B,E,F,G,C,H,D 和 A,E,F,B,I,G,H,C,D 试画出该二叉树。1. 设电文中出现字字母A、B、C、D、E、F

18、、G、H每个字母在电文中出现的次数分别是5，25，4，7，9，12，30，8，请画出哈夫曼树，求A,B,C,D的哈夫曼编码及哈夫曼树的WPL。2.试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。 (1)试画出插入完成之后的二叉排序树； (2)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。 (3)对该树进行中序遍历,试写出中序遍历序列。4.已知一个网的邻接矩阵，画出它的关键路径。aij=0表示节点i到节点j没有有向边aij=k，表示<i,j>的权为k。0645000

19、000000100000000100000000020000000009700000000400000000020000000040000000003.比较顺序存储、链式存储和哈希存储等几种存储模式六、阅读题（本大题共3小题，每小题5分，共15分）1该算法是用折半查找法在一有序数组中查找key。若找到，返回其下标值，否则返回-1。将算法填充完整。int BinSearch(DataType list,int low,int high,DataType key) int mid; DataType midvalue; while(low<=high) mid=(low+high)/2; m

20、idvalue=listmid; if (key=midvalue) return mid; else if(key<midvalue) high=_mid_ else low=_mid_ return 1;2阅读下面的算法      void mynote(LinkList &L)       /L是不带头结点的单链表的头指针           &#

21、160; if(L&&L->next)                   q=L；L=L>next；p=L；        while(p>next) p=p>next；        p>next=q；q>next=NULL

22、；                             设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。a2,.,an,a13已知二叉树的存储结构为二叉链表，阅读下面算法。      typedef struct nod

23、e          DateType data；         Struct node * next；      ListNode；      typedef ListNode * LinkList ；      LinkList Leafhead=NUL

24、L；      void Inorder (BinTree T)                     LinkList s；            If(T)     

25、;           Inorder(T>lchild)；                If (!T>lchild)&&(!T>rchild)            

26、60;        s=(ListNode*)malloc(sizeof(ListNode)；                     s>data=T>data；            

27、0;        s>next=Leafhead；                     Leafhead=s；                 &#

28、160;                     Inorder(T>rchild)；                          

29、60;     对于如下所示的二叉树                           画出执行上述算法后所建立的结构； 七、算法设计题（选一题，本题共9分）1. 设n个元素的线性表顺序存储在一维数组st1.maxlen的前n个位置上,试将新元素e插入表中第i-1个和第i个元素之间,写出算法。#include <stdio.h>int insert(int arr, int index, int maxlen, int value) int start_index = index-1; for (int i = max