第五套B - 数据结构- 浙江万里学院

1、 班级： 学号： 姓名： 装订线浙江万里学院 学年第 学期 试卷（ 卷）考试时间：_120_分钟 闭 卷班级： 学号： 姓名： 成绩： 一、 单项选择:（每空2分，共30分）123445678910111213141. 在数据结构的讨论中把数据结构从逻辑上分为 . A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构 2.链表不具备的特点是： A可随机访问任何一个元素B插入、删除操作不需要移动元素C无需事先估计存储空间大小D所需存储空间与线性表长度成正比3. 带头结点的单链表head为空的判定条件是_。A. head= =NULL B. head-

2、>next= =NULLC. head->next= =head D. head!=NULL4. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为_。 A. i B. n=i C. n-i+1 D. 不确定5. 栈的特点是_，队列的特点是_。 A. 先进先出 B. 先进后出6设有两个串p和q，求q在p中首次出现的位置的运算称作_。A. 连接 B. 模式匹配C. 求子串 D. 求串长7. 二维数组A中，每个元素Aij的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A47的起

3、始地址为_。A. SA+141 B. SA+180 C. SA+222 D. SA+2258. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca9在一非空二叉树的中序遍历序列中，根结点的右边_。A. 只有右子树上的所有结点 B. 只有右子树上的部分结点C. 只有左子树上的部分结点 D. 只有左子树上的所有结点10. 具有6个顶点的无向图至少应有_条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 811. 二分查找和

4、二叉排序树的时间性能_。A. 相同 B. 不相同12. 采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为_。AO（n2） B. O(nlog2n) C. O(n) D. O(log2n)13. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序14. 下面的序列中_是大顶堆积。 A.1,2,8,5,3,9,10,4 B. 1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1 D. 9,8,7,6,5,4,3,1二、填空:（每空2分, 共20分）1. 若频繁地对线性

5、表进行插入与删除操作，该线性表应采用_存储结构。2. 在双链表中，每个结点有两个指针域，一个指向_ _，另一个指向_ _。3. 空格串是_ _，其长度等于_ _。4. 一个图的 表示法是唯一的，而 表示法是不唯一的。5. 对于长度为n的关键字有序的线性表，若进行顺序查找，则时间复杂度为_ _；若采用二分法查找，则时间复杂度为_ _；6.三、用图表回答下列问题:（每题10分, 共20分） 1.有如下图所示线性表，经过daorder 算法处理后，线性表发生了什么变化。画出处理后的线性表。(设顺序表类是SqList，函数daorder()是类的公有成员函数。) void SqList:daorder

6、() int i, j, n ; ElemType x;n=length/2; for( i=0 ; i<n; i+ ) j=length-i-1; x=elemi; elemi=elemj; elemj=x; elem0 elem7 /假设length=8 3画出下列图的邻接链表，写出各顶点的度。 V1 V2 V5 V3 V4四、阅读下列算法，分析它的作用：（每小题10分，共20分）/ 类定义const int MAX=20;typedef char ElemType ;class Sqstack private:ElemType elem MAX;int top ; public:S

7、qstack()top=0;ElemType pop();void push(ElemType x);/.; ;1. 阅读下列算法，说明该算法的作用。void Sqstack:push(ElemType x ) if ( top=MAX-1 )cout<<”n 满！”；else top+; elemtop=x; / push struct Snode /结点结构 char data; Snode *next ; ;class Link /链表类 private:Snode *Head; public:Link ()Head =NULL;void creat();void output();/.;2. 有如下图所示单链表，经过output（）算法处理后，单链表发生了什么变化 ？画出处理后的单链表图示。void Link :output() p=Head->next; while( p !=NULL) cout<<”n data=”<<p->data ; p=p->next; /output aHeadbced五、算法设计题（共10分 ）请注意答题基本要求：画出图示，写出算法1. 有一个递增单链表（允许出现值域重复的结点），设计一个算法删除值域重复的结点。 提示：结点存储结构为：struct NodeType ElemTyp