数据结构-试题

1、.西南科技大学网络教育学院 重修补考试题单课程名称：数据结构专业班级： 命题教师：孙敏学生姓名 学 号: 成 绩 考试时间 月 日 第1页 共4 页一. 填空题(每空2分,共20分)1. 数据元素是_的基本单位2. 数据结构被形式的定义为(D,S),其中D是_的有限集合,S是D上_的有限集合3. 计算机算法指的是_,它的五个特性有:有穷性,_,_,输入,输出.4. 向一个长度为n的向量中删除第i个元素(1<=i<=n)时,需向前移动_个元素5. 单链表是_的链接存储表示6. 一棵有k层的满二叉树一共有_个结点,如果它是一棵完全二叉树,则至少有_个结点.二. 选择题 (每题3分,共3

2、0分)1. 计算机算法指的是_ A) 计算方法 B) 排序方法 C) 解决问题的有限操作序列 D) 调度方法2. 线性结构通常采用的两种存储结构是_。 A) 顺序存储结构和链式存储结构 B) 散列方式和索引方式C) 链表存储结构和数组 D) 线性存储结构和非线性存储结构3. 一个栈的入栈序列是a, b, c, d, e, 则出栈的不可能的输出序列是_A) edcba B) dceba C) dceab D) abcde4. 设n, m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是_。A) n在m的右方 B） n是m的祖先 C）n 在m的左方 D） n是 m的子孙5. 对线性表进行二分

3、查找时，要求线性表必须_。 A） 以顺序方式存储 B） 以顺序方式存储，且结点关键字有序排序 C） 以链接方式存储 D） 以链接方式存储，且结点关键字有序排序6.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。A) s->next=p; p->next=s; B) s->next=p->next; p->next=s;C) s->next=p->next; p=s; D) p->next=s; s->next=p;7.具有4个顶点的无向完全图有_条边。A) 6 B) 12 C) 16 D) 208.栈和队列的共同

4、点是_。 A)都是先进后出 B) 只允许在端点处插入和删除 C) 没有共同点 D)都是后进先出9.串是一种特殊的线性表，其特殊性体现在_。A) 可以顺序存储 B) 数据元素是一个字符C) 可以链接存储 D) 数据元素可以是多个字符10.在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。A) 1 B) 2 C) 4 D) 1/2三、判断题（每小题1分，共10分）1. 二维数组可以视为数组元素为一维数组的一维数组。 （ ）2. 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，通常存储器中还有空闲存储空间，就不会产生存储溢出的问题。 ( )3. 在用单链表表示的链式队列中，队头在

5、链表的链尾位置。 ( ) 4. 凡是递归定义的数据结构都可以用递归算法来实现它的操作。 ( )5. 当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。 ( )6. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。 ( )7. 进行折半搜索的表必须是顺序存储的有序表。 ( )8. 一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。 ( )9. 在散列法中采取开散列（链地址）法来解决冲突时，其装载因子的取值一定在（0，1）之间。 ( ) 10. 快速排序肯定是最快的排序方法( )三解答题（40分）AB

6、CGFHDEIKJML1.已知有序序列3,12,24,37,45,53,61,78,90,100,请用二分查找法查找 元素37,并写出每次查找比较的过程,用”标示 查找过程的mid元素,分别用” 和 ”标示low和high元素(10分)2由如右图所示的树,回答以下问题:（6分）(1) 该树的深度是_(2) 该树的度是_(3) 该树的叶子结点有哪些_3.阅读下面的算法程序,补上空格处的语句(每空2分，共6分)typedef struct Elemtype *elem; /数据元素存储空间基址,建表时按实际长度分配,0号单元留空 int length; /表长度SSTable; /静态查找表的顺序

7、存储结构 int Search_Bin(SSTable St,KeyType key)/关键字从小到大排好 low=1;high=St.length; while(low<=high)mid=(low+high)/2;if EQ(key,St.elemmid.key) return _;else if LT(key,St.elemmid.key) _; / LT 表示第一个参数值比第二个小 else _;return 0;/Search_Bin4. 说明下列归并过程的功能(10分)void unknown(BinTreeNode * T,int i)/ 指针T是完全二叉树的根指针。if

8、(T ! = NULL) count << Tdata << ” ,” << i <<endl; unknown(T leftChild , i+1 ); unknown(T rightChild , i+1 ); 主程序调试方式unknown (BT.root, 0 ) /二叉树根结点的层次号为，其他结点的层次号等于其双亲的层次号加一。5假定用于通信的电文由个字母a,b,c,d,e,f,g,h组成，各字母在电文中出现的频率分别为，。试为这个字母设计不等长Huffman编码，并给出该电文的总码数。（8分）a b c d e f g h电文总长度：

9、答案一填空题(1空2 分 共20分) 1数据 2.数据元素,关系3.有若干条指令组成的有穷序列，可执行性,确定性4.n-i5.线性表6. 2k-1,2(k-1)二 选择题 (每题3分,共30分)CACCB,BABBB三 判断题（10分）1. 2. 3.× 4. 5. 6. 7. 8.× 9.× 10. ×四 解答题（40分）1(8 分)原始:31224374553617890100 lowmid high第一次后31224374553617890100 lowmidhigh 第二次后31224374553617890100 lowhigh 第三次后31224374553617890100 lowhighmid经过3次比较后，找到了元素372 4， 4， C F G L I M K （每个2分，共6分）3 return 1， high=mid-1， low=mid+1 （每个2分，共6分）4以前序顺序输出用