嘉兴学院试卷
2012 —2013学年第2学期期中考试试卷
课程名称：数据结构 使用班级：信计11级 考试形式：闭卷
题号 一 二 三 四 五 总分 得分 评阅人 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每个选择1分，共10分)
1．抽象数据类型可用三元组（D，R，P）表示，其中R是 D 的有限集。 A．算法 B．数据元素 C．数据操作 D．数据关系
2．数据结构的研究包含三个方面的内容，它们分别是数据的 B 、数据的存储结构和数据运算。 A．数据元素 B．逻辑结构 C．存储结构 D．计算方法
3．线性结构的顺序存储结构是一种随机存取的存储结构，而链式存储结构是一种 A 的存储结构。 A．顺序存取 B．随机存取 C．索引存取 D．散列存取 4．线性表L在 B 情况下，最适合使用链接结构实现算法。
A．不需经常对L进行修改 B．需经常对L进行删除和插入 C．需经常修改L中结点值 D．L中结点结构复杂 5．一个队列的入列序列是a，b，c，d，则队列的输出序列是 A 。
A．a，b，c，d B．a，d，c，b C．c，b，d，a D．d，c，b，a
6．循环队列Q中的数据元素值存放在长度为m的数组中，且此数组最多只能存放m-1个数据元素。已知头尾指针分别是Q．front和Q．rear, 则判断Q为满队列的条件是 B 。 A．Q．front= =Q．rear B． Q．front= =(Q．rear+1) %m C．Q．front!=Q．rear D． Q．front!= (Q．rear+1) %m 7．一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的输出序列是 D 。 A．abcde B．decba C．edcba D．dceab
8．判定一个顺序栈S（最多存放元素个数是m）为空栈的条件是 C 。 (顺序栈类型定义为： typedef struct {
Selemtype *base; Selemtype *top;
Int stacksize; } Sqstack； )
A．S．top= =0 B． S．top= =m C． S．top= = S．base D． S．base= =0
9．从数据结构来看，串是一种特殊的线性表，其特殊性体现中 B 。 A．可以顺序存储 B．数据元素是一个字符
C．可以链式存储 D．数据元素可以是多个字符。 10.下列（ D ）是稀疏矩阵的一种压缩存储方法。 A．顺序表 B．单链表
C．双向链表 D．三元组的顺序表。
二、填空题（20分，每空1分）
1．在一个长度为n的顺序表中插入第i个元素(1≤i≤n)时，需向后移动__n-i+1_ 个元素。 2．基本线性表、栈和队列都属于线性结构。对于线性表可以在 任意 位置插入和删除元素；对于栈只能在 栈顶(表尾) 插入和删除元素；对于队列只能在 队尾(表尾) 插入元素和 队首(表头) 删除元素。
3．假设按低下标优先存储整数数组A9×8×7×6时，第一个元素的字节地址是100，每个整数占四个字节，则a3×2×1×5的存储地址是 4512 。
4．假设以一维数组S [m]作为n阶对称矩阵A的压缩存储结构, 则m的最小值应为： n(n+1)/2 ，又假设下三角矩阵A中的元素a i j (0= 当i>=j时，k= i *(i+1)/2+j ，当i 5．已知P结点是某双向链表的中间结点，则在P结点之前插入S结点时修改链的语句序列是： (双向链表的存储结构描述为：typedef struct Dulnode { elemtype data; struct Dulnode *piror; struct Dulnode *next; }Dulnode,*Dulinklist; ) 1） S->prior=P->prior ; 2） P->prior->next=S ; 3） S->next=P; 4） P->prior=S; 6．在一个栈顶指针为S的链栈中插入一个P所指结点时，则插入时修改链的语句序列是： 1） P>next=S ; 2） S=p ; 7．如果循环队列的存储结构描述如下： #define MAXSIZE 10 //最大队列长度 typedef struct { Qelemtype *base; int front; int rear; }Sqqueue; 则一个已知循环队列Q的长度为 (Q.rear-Q.front+MAXSIZE) / 10 。 8．常用的两种存储结构是 顺序存储 和 链式存储 。 9．按数据元素的逻辑关系来系，数据结构可分为四种：线性表、集合、树和图。其中树形结构中的数据元 素之间存在“ 一对多 ”的关系 。 10．在一个单链表中，若删除p所指结点的后继结点，则修改链的语句是： p->next=p->next->next ; 。 3．对线性表A=（23, 17, 28, 69,11），画出下列存储结构的示意图： （共6分） （1）不带表头结点的单链表； 三、判断题（共10分，2分1题，对的打“√”，错的打“×”） （2）带表头结点的单向循环链表； 1. 线性表的逻辑顺序与存储顺序总是一致的。 （ × ） （3）带表头结点的双向循环链表。 2．链式存储时，存储区域可以连续，也可以不连续。 （ √ ） 解: (1) 不带表头结点的单链表为: 3．模式匹配中的KMP算法的最大特点是指示主串的指针不需要回溯。 （ √ ） L 23172869114．判断一个循环队列Q为空的条件是Q.front=Q.real=0。 （ × ） 5．二维数组是以一维数组为数组元素的线性表，因此它是线性结构。 （ √四、应用与计算题（共26分） 1． 求下列程序段的时间复杂度。（9分） （1） for (i=0; i (2) 带表头结点的单向循环链表为: L 2317286911 (3) 带表头带表头结点的双向循环链表为: L 2317286911 4. 建立链栈的基本思想是从空栈开始依次将入栈元素结点插入到栈顶。假设依次入栈的元素为23、17、28、 69、11，请画出将各元素结点分别入栈后的链栈示意图。（5分） 解: 示意图如下: top23 top^1723 top^ 281723 top^ 69281723 top^ 1169281723 ^ 五、 根据以下各题的要求，分别写出相应的算法（用类C语言）。（共34分） 1． 试写一算法实现在有序顺序表中插入一个值为x的元素，并使顺序表仍保持有序。（8分） （已知顺序表采用的数据结构描述为： typedef struct { Elemtype *elem; int length; int listsize; }Sqlist; ） 解:算法如下: status Insert_SqList(SqList &L, int x) //把x插入递增有序表L中 { if(va.length+1>va.listsize) return ERROR; //分配空间满时，则退出。 for(i=L.length-1; i>=0 && L.elem[i]>x;i--) L.elem[i+1]=L.elem[i]; //一边比较，一边进行后移 L.elem[i+1]=x; //插入x L.length++; //表长加1 return OK; } 2．写一算法，将以单链表存储的线性表中所有值为x的元素删去。（8分） （已知单链表采用的数据结构描述为： typedef struct Lnode{ Elemtype data; struct Lnode *next;}Lnode,*Linklist; ） 解: 算法如下: status delete(Linklist &L, Elemtype x)//假设单链表带表头结点 { if (L->next==NULL) return ERROR; //链表为空 P=L; while(p->next) if (p->next->data= =x) { q=p->next; p->next=q->next; free(q); } else p=p->next; return OK; } 3．编写一个函数判断一个字符序列是否为回文序列，所谓回文序列就是正读与反读都相同的字符序列， 例、如：abba和abdba均是回文序列。要求只借助栈来实现。 (8分) 解:算法如下: int palindrome(char text[],int n){ //如果是回文，则返回1值，否则，返回0值。 int i; char e; Sqstack s=init_stack(s); //创建一个空的顺序栈 for(i=0;i s=push(s,text[i]); //将文本字符依次入栈 } for (i=0;i s=pop(s,&e); //再将栈中的字符依次弹出并与原文本字符逐一进行比较 if (text[i]!=e) break; } if (i= =n) return 1; else return 0; } 4. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试 编写相应队列的入队和出队的算法。（10分） （已知循环链队列采用的数据结构描述为： typedef struct Qnode{ Elemtype data; struct Qnode *next;}Qnode,*LinkQeueu; ） 解: 入队操作算法： void EnCiQueue(LinkQueue &rear, Elemtype x) //把元素x插入循环链表表示的队列rear, rear指向队尾元素, //rear->next指向头结点, rear->next->next指向队头元素 { p=(LinkQnode*)malloc(sizeof(Qnode)); p->data=x; //产生一个新结点p p->next=rear->next; //直接把p加在rear的后面 rear->next=p; rear=p; //修改尾指针 }