第一篇：数据结构试卷及参考答案_2
数据结构试卷
（二）一、选择题(24分)1．下面关于线性表的叙述错误的是（）。
(A)线性表采用顺序存储必须占用一片连续的存储空间
(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现
2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
(A)2m-1(B)2m(C)2m+1(D)4m 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。
(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
(A)BADC(B)BCDA(C)CDAB(D)CBDA 5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1 6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
(A)9(B)10(C)11(D)12 7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
(A)n-1(B)n(C)n+1(D)2n-1 8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8
二、填空题(24分)1.为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。
2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”);else {____________________;_________________;} } 3.中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。4.快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。
5.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。6.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。7.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为___________________________。
8． 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是，BFS遍历的输出序列是
三、应用题(36分)1． 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
2． 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。3． 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
4． 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。5． 设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。
6． 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。
四、算法设计题(16分)
1． 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
2． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。
数据结构试卷
（二）参考答案
一、选择题
1.D 2.B 3.C 4.A 5.A 6.C
二、填空题
1.构造一个好的HASH函数，确定解决冲突的方法 2.stack.top++，stack.s[stack.top]=x 3.有序
4.O(n2)，O(nlog2n)5.N0-1，2N0+N1
6.d/2 7.(31，38，54，56，75，80，55，63)8.(1，3，4，5，2)，(1，3，2，4，5)
三、应用题
1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.3.4.5.6.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;2,ASL=91*1+2*2+3*4+4*2)=25/9 树的链式存储结构略，二叉树略
E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 略
7.B
8.C
四、算法设计题
1.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。void quickpass(int r[], int s, int t){
int i=s, j=t, x=r[s];
while(i while(i } r[i]=x;} 2.设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。 typedef struct node {int data;struct node *next;}lklist;void intersection(lklist *ha,lklist *hb,lklist *&hc){ lklist *p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){ for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=0){ t=(lklist *)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;} } } 一、选择题（每小题2分，共30分）1.数据结构是（D）。 A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．以下与数据的存储结构无关的术语是（D）。 A．链队列 B.链表 C.顺序表 D.栈 3．以下数据结构中，（A）是非线性数据结构 A．树 B．字符串 C．队 D．栈 4．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。 A．98 B．100 C．102 D．106 5．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。A．插入 B．删除 C．排序 D．查找 6．线性表采用链式存储时，其地址(D)。 A．必须是连续的 B．一定是不连续的 C．部分地址必须连续 D．连续与否均可以 7．线性表是(A)。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 8．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）。 A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1 9.若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C）。 A．k B．n-k-1 C．n-k+1 D．不确定 10.对于队列操作数据的原则是（A）。 A.先进先出 B.后进先出 C.先进后出 D.不分顺序 11.栈和队列的共同点是（C）。 A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点 12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（A）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13.空串与空格串（B）。 A．相同 B．不相同 C．可能相同 D．无法确定 14.串与普通的线性表相比较，它的特殊性体现在（C）。A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意 15.串的长度是指（B）。 A.串中所含不同字母的个数 B.串中所含字符的个数 C.串中所含不同字符的个数 D.串中所含非空格字符的个数 二、填空题（每空2分，共20分） 1． 线性表、栈和队列，串都是__线性_____结构。2． 数据的基本单位是__数据元素_______________。 3． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序______存储结构。4． 已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为Loc(a1)，那么，第i个元素的存储地址Loc(ai)= Loc(a1)+(i-1)*k。5． 栈（stack）是限定在表尾进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__栈顶________，而另一端称为_栈底________。6． 一个循环队列Q中，头指针和尾指针分别为Q.front和Q.rear，且最大队列长度为MaxQSize，则判断队空的条件为 Q.rear==Q.front,判断队满的条件为(Q.rear+1)%MaxQSize==Q.front。队列的长度为(.rear-Q.front+MaxQSize)%MaxQSize 7． 两个串相等的充分必要条件是 两个串的长度相等，且各个对应位置的字符都相等。 三、程序填空题（每空3分，共30分） 1.在带头结点的单链表L中第i个数据元素之前插入数据元素e的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 typedef struct node {int data； struct node *next； }linknode,*link； int ListInsert_L(link &L, int i, int e){ Linknode *p；int j； p = L； j = 0； while(p && j < i-1){ p=p->next ； ++j； } // 寻找第i-1个结点 if(!p || j > i-1)return 0； s=(link)malloc(sizeof(linknode))；// 生成新结点s s->data = e； s->next=p->next ； p->next = s； // 插入L中 return 1； } 2.对顺序栈的C语言描述算法如下，其中top为栈顶指针，请填充算法中标出的空白处，插入元素e为新的栈顶元素。 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *base;char *top;int stacksize;}SqStack; int Push(SqStack &S, char e){ // if((s.top-s.base)>=s.stacksize)//栈满，追加存储空间 { S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType))； if(!S.base)return 0； S.top = s.base+s.stacksize ； //修改栈顶指针 S.stacksize += STACKINCREMENT； } *s.top++=e ；//插入元素 return 1； } 3.对链队列的C语言描述算法如下，请填充算法中标出的空白处，删除队列Q 的队头元素并用e返回其值。typedef struct QNode{ QElemType data； struct QNode *next； }QNode, *QueuePtr； typedef struct { QueuePtr front； QueuePtr rear； }LinkQueue； int DeQueue(LinkQueue &Q, QElemType &e){ Linknode *p； if(Q.front==Q.rear)retrun 0；//队列空，返回 p = Q.front-> next； e = p->data； Q.front-> next=p->next；//修改指针 if(Q.rear==p)Q.rear= Q.front ； //队列只有一个元素的情况 free(p)；//释放结点空间 return 1； } 三、算法设计与分析题（每题10分，共20分） 1、简述下列算法实现的功能：（每题5分，共10分）（1）typedef struct LNode{ Char data; struct LNode *next;}LNode,*LinkList;LinkList Demo(LinkList &L){ // L 是无头结点单链表 LNode *Q,*P;if(L&&L->next){ Q=L;L=L->next;P=L;while(P->next)P=P->next; P->next=Q;Q->next=NULL; } return L;}// Demo 答：将单链表的第一个结点删除，放到链尾。 ——————————————————————————————————————————————————— （2）#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;int *top;int stacksize; } Stack;void Demo1(Stack &S, int m){ Stack T;int i; InitStack(T);//初始化栈 while(!StackEmpty(S))//判断栈是否为空 if((i=Pop(S))!=m)Push(T,i);//入栈操作 while(!StackEmpty(T)) { i=Pop(T);//出栈操作 Push(S,i); } } 答：删除栈S中所有值为m的数据元素 2.有一个带头结点的单链表，头指针为head，编写一个算法计算所有数据域为X的结点的个数（不包括头结点）。typedef struct node {int data;struct node *next;}linknode,*link;int sample(link head, int X){ int count=0;link p=head->next;while(p){if(p->data==X)count++;p=p->next;} return count;} 数据结构试卷 （一）一、选择题（20分） 1．组成数据的基本单位是（）。 (A)数据项(B)数据类型(C)数据元素(D)数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。 (A)线性结构(B)树型结构(C)图型结构(D)集合 3．数组的逻辑结构不同于下列（）的逻辑结构。 (A)线性表(B)栈(C)队列(D)树 4．二叉树中第i(i≥1)层上的结点数最多有（）个。 ii-1(A)2i(B)2(C)2(D)2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。 (A)p->next=p->next->next(B)p=p->next (C)p=p->next->next(D)p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。 (A)6(B)4(C)3(D)2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。 (A)100(B)40(C)55(D)80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。 (A)3(B)4(C)5(D)1 9．根据二叉树的定义可知二叉树共有（）种不同的形态。 (A)4(B)5(C)6(D)7 10.设有以下四种排序方法，则（）的空间复杂度最大。 (A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序 二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]){ i=j=0;while(i 三、应用题（30分） 1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。 2．设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 3．设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。 4．设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。5．设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树。 四、算法设计题(20分)1.设计判断单链表中结点是否关于中心对称算法。2.设计在链式存储结构上建立一棵二叉树的算法。3.设计判断一棵二叉树是否是二叉排序树的算法。 数据结构试卷 （一）参考答案 一、选择题 1.C 2.C 3.D 4.C 5.A 6.C 7.C 8.B 9.B 10.B 二、填空题 1.(F+1)% m 2.O(n)，O(n)3.2n，n+1 4.s->next=p->next;s->next=s 5.n, 2e 6.m=2e 7.CBA 8.4，16 9.i-j+1，0 10.n-1 三、应用题 1.链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。2.哈夫曼树略，WPL=78 3.(18,5,16,19,21,23)，(5，16，21，19，18，23) h0h18h2012345674.线性探测： 链地址法：h310 81025322768h42532h568h6275.深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)} 四、算法设计题 1.设计判断单链表中结点是否关于中心对称算法。 typedef struct {int s[100];int top;} sqstack;int lklistsymmetry(lklist *head){ sqstack stack;stack.top=-1;lklist *p; for(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;} for(p=head;p!=0;p=p->next)if(p->data==stack.s[stack.top])stack.top=stack.top-1;else return(0); return(1);} 2.设计在链式存储结构上建立一棵二叉树的算法。 typedef char datatype;typedef struct node {datatype data;struct node *lchild,*rchild;} bitree;void createbitree(bitree *&bt){ char ch;scanf(“%c”,&ch); if(ch=='#'){bt=0;return;} bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchild);createbitree(bt->rchild);} 3.设计判断一棵二叉树是否是二叉排序树的算法。 int minnum=-32768,flag=1;typedef struct node{int key;struct node *lchild,*rchild;}bitree;void inorder(bitree *bt){ if(bt!=0) {inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);} } 广东海洋大学 2013 —— 2014 学年第 1 学期 《数据结构与算法》课程试题 一、选择题（6小题，每题3分） 1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用（A)存储方法最节省时间 A 顺序表 B单链表 C 双链表 D单循环链表 2.一个栈的入栈序列是1,2,3,4,5，则不可能的出栈序列是(C)A 5,4,3,2,1 B 4,5,3,2,1 C 4,3,5,1,2 D 1,2,3,4,5 3.深度为k的完全二叉树至多有（C）个结点 A 2k2 1B 2k1 C D 2k11 k4.G是一个非连通无向图，共28条边，则该图至少有（D）个顶点2A 6 B 7 C 8 D 9 1 5.在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（C）型调整以使其平衡 A LL B LR C RL D RR 6.下述排序方法中，时间性能和待排序记录的初始状态无关的是（C）A 插入排序和快速排序 B 归并排序和快速排序 C 选择排序和归并排序 D 插入排序和归并排序 二、填空题 1.数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素位置，计算队列中元素个数的公式为______（rear-front+n）%n______________。 2.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有__12_________个叶子结点。 3.已知无向图的顶点数为n，边数为e，其邻接表表示的空间复杂度为____________O(n+e)____。4.假定一个数列{25,43,62,31,48,56}，采用散列函数为H(k)=k mod 7，则元素48的同义词是____62_______。5.利用简单选择排序对n个记录进行排序，最坏情况下，记录交换次数为_____n-1_______。 三、（15分）已知一棵二叉树的中序遍历序列为DBKEHJAFCIG，后序遍历序列为DKJHEBFIGCA，试画出该二叉树并给出其前序遍历序列 四、（15分）设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，它们在电文中出现的频度分别为{0.02,0.30,0.08,0.14,0.17,0.11,0.12, 0.06}，回答下面问题：（1）为这八个字符设计哈夫曼编码（2）对这八个字符进行等长编码需要几位二进制数，哈夫曼编码比等长编码电文总长压缩多少？ 五、（20分）已知一个长度为11的线性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，试回答下面问题（1）将线性表元素依次插入一个空的平衡二叉树，画出所得平衡二叉树，如果假设每个元素查找概率相同，则平均查找长度为多少？ （2）如果对线性表元素排序后进行折半查找，画出折半查找判定树，假设每个元素查找概率相同，计算平均查找长度。 六、（12分）已知数据序列为（11,4,8,19,6,31,23），写出快速排序及堆排序每一趟的结果 解： 七、（11分）设单链表以非递减有序排列，设计算法实现在单链表中删除值相同的多余结点。 数据结构试卷 （八）一、选择题(30分)1.字符串的长度是指（）。 (A)串中不同字符的个数(B)串中不同字母的个数 (C)串中所含字符的个数(D)串中不同数字的个数 2.建立一个长度为n的有序单链表的时间复杂度为（）(A)O(n)(B)O(1)(C)O(n)(D)O(log2n)3.两个字符串相等的充要条件是（）。 (A)两个字符串的长度相等(B)两个字符串中对应位置上的字符相等 (C)同时具备(A)和(B)两个条件(D)以上答案都不对 4.设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。 (A)99(B)97(C)91(D)93 5.在二叉排序树中插入一个关键字值的平均时间复杂度为（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。 (A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。 (A)8(B)7(C)6(D)5 8.设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（）个度数为0的结点。 (A)5(B)6(C)7(D)8 9.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。 (A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.队列是一种（）的线性表。 (A)先进先出(B)先进后出(C)只能插入(D)只能删除 二、判断题(20分)1.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）2.设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（）3.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（）4.二维数组和多维数组均不是特殊的线性结构。（） 5.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）6.如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）7.非空的双向循环链表中任何结点的前驱指针均不为空。（）8.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（） 9.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）10.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（） 三、填空题(30分)1． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_____________________________。2． 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next;_________________。4． 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。 5． 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。 6． 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。 7． 设有向图中不存在有向边 8． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_____________________________。 9． 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。10． 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换即可。 四、算法设计题(20分)1.设计一个在链式存储结构上统计二叉树中结点个数的算法。2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 数据结构试卷 （八）参考答案 一、选择题 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A 二、判断题 1．对 2．错 3．对 4．错 5．错 6．对 7．对 8．对 9．对 10．对 三、填空题 1.(49，13，27，50，76，38，65，97)2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.p->next=s 4.head->rlink，p->llink 5.CABD 6.1，16 7.0 8.(13，27，38，50，76，49，65，97)9.n-1 10.50 四、算法设计题 1.设计一个在链式存储结构上统计二叉树中结点个数的算法。 void countnode(bitree *bt,int &count){ if(bt!=0) {count++;countnode(bt->lchild,count);countnode(bt->rchild,count);} } 2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 typedef struct {int vertex[m];int edge[m][m];}gadjmatrix;typedef struct node1{int info;int adjvertex;struct node1 *nextarc;}glinklistnode;typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){ int i,j;glinklistnode *p;for(i=0;i<=n-1;i++)g2[i].firstarc=0;for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){ p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;} }第二篇：数据结构期中试卷及答案
第三篇：数据结构试卷(一)及答案
第四篇：广东海洋大学数据结构试卷及答案
第五篇：数据结构试卷(八)及答案
点击咨询 