第一篇：数据结构试卷及参考答案_9
数据结构试卷
（九）一、选择题(30分)1．下列程序段的时间复杂度为（）。
for(i=0； i for(i=0； i (A)O(m*n*t)(B)O(m+n+t)(C)O(m+n*t)(D)O(m*t+n)2．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。 (A)n-i(B)n+l-i(C)n-1-i(D)i 3．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。 (A)N1-1(B)N2-1(C)N2+N3(D)N1+N3 4．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。 (A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)5．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。 (A)p->right=s； s->left=p； p->right->left=s； s->right=p->right； (B)s->left=p；s->right=p->right；p->right=s； p->right->left=s； (C)p->right=s； p->right->left=s； s->left=p； s->right=p->right； (D)s->left=p；s->right=p->right；p->right->left=s； p->right=s； 6．下列各种排序算法中平均时间复杂度为O(n2)是（）。 (A)快速排序(B)堆排序(C)归并排序(D)冒泡排序 7．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 (A)n-i(B)n-1-i(C)n+l-i(D)不能确定 8．设散列表中有m个存储单元，散列函数H(key)= key%p，则p最好选择（）。 (A)小于等于m的最大奇数(B)小于等于m的最大素数 (C)小于等于m的最大偶数(D)小于等于m的最大合数 9．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。 (A)4(B)5(C)6(D)7 10.设完全无向图中有n个顶点，则该完全无向图中有（）条边。 (A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/2 11.设顺序表的长度为n，则顺序查找的平均比较次数为（）。 (A)n(B)n/2(C)(n+1)/2(D)(n-1)/2 12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 (A)1(B)2(C)3(D)4 13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。 (A)6(B)11(C)5(D)6.5 14.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。(A)1，2，3，4(B)2，3，4，1(C)1，4，2，3(D)1，2，4，3 15.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（）。 (A)4(B)5(C)6(D)7 二、填空题(30分)1． 设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为： 1)s->next=___________；2)p->next=s；3)t=p->data； 4)p->data=___________；5)s->data=t； 2． 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。3． 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。 4． 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。 5． 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的角度来考虑则最好选择________排序。 6． 设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。 7． 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。 8． 设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。 9． 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_______________________。10． 设无向图G（如右图所示），则其最小生成树上所有边的权值之和为_________________。 三、判断题(20分)1． 有向图的邻接表和逆邻接表中表结点的个数不一定相等。()2． 对链表进行插入和删除操作时不必移动链表中结点。()3． 子串“ABC”在主串“AABCABCD”中的位置为2。()4． 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。()5． 希尔排序算法的时间复杂度为O(n2)。()6． 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。()7． 中序遍历一棵二叉排序树可以得到一个有序的序列。()8． 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。()9． 顺序表查找指的是在顺序存储结构上进行查找。（）10． 堆是完全二叉树，完全二叉树不一定是堆。（） 五、算法设计题(20分)1． 设计计算二叉树中所有结点值之和的算法。2． 设计将所有奇数移到所有偶数之前的算法。3． 设计判断单链表中元素是否是递增的算法。 数据结构试卷 （九）参考答案 一、选择题 1．A 2．A 6．D 7．C 11．C 12．C 3．A 8．B 13．D 4．C 9．C 14．A 5．D 10．A 15．A 二、填空题 1.p->next，s->data 2.3.4.5.6.7.8.9.50 m-1 6，8 快速，堆 19/7 CBDA 6(24，65，33，80，70，56，48)10.8 三、判断题 1．错 2．对 3．对 4．对 5．错 6．错 7．对 8．对 9．错 10．对 四、算法设计题 1． 设计计算二叉树中所有结点值之和的算法。 void sum(bitree *bt,int &s){ if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} } 2． 设计将所有奇数移到所有偶数之前的算法。void quickpass(int r[], int s, int t){ int i=s,j=t,x=r[s]; while(i while(i while(i } r[i]=x;} 3． 设计判断单链表中元素是否是递增的算法。int isriselk(lklist *head){ if(head==0||head->next==0)return(1);else for(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);return(1);} 一、选择题（每小题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;} 2014－2015学第一学期《数据结构》 期中考试试卷 一、选择题（每题2分，共20分） 1.计算机内部数据处理的基本单位是（B）。 A.数据 B.数据元素 C.数据项 D.数据库 2.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。 for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O(n)C.O(n) D.O(n) 33.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（A）个元素。 A．n-i B．n-i+l C．n-i-1 D．i 4.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（B）。 A．s->next=p->next;p->next=s B．q->next=s;s->next=p C．p->next=s->next;s->next=p D．p->next=s;s->next=q 5.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。C A．top不变 B．top=0 C．top--D．top++ 6.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。D A．rear％n= = front B．（front+l）％n= = rear C．rear％n-1= = front D．(rear+l)％n= = front 7.两个字符串相等的条件是（D）。 A.两串的长度相等 B.两串的长度相等，并且两串包含的字符相同 C.两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 8.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（C）。A.SA+141 B.SA+144 C.SA+222 D.SA+225 9.设有广义表D=(a,b,D)，其长度为（B），深度为（A）。A.无穷大 B.3 C.2 D.5 10.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（B）个。 A.15 B.16 C.17 D.47 二、填空题（每空1分，共20分） 1.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。2.集合，线性，树，图 2.一个算法的效率可分为__________________效率和__________________效率。4.时间，空间 3.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。7．顺 （第1页，共3页） 序，链接 4.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。12．O(1)，O(n)5.可以在线性表的______位置插入和删除元素；对于栈只能在_______位置删除元素；对于队列只能在_______位置插入元素。9任何，栈顶，队尾 6.设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。3.“BCDEDE” 7.一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。1.线性结构，顺序结构，以行为主序，以列为主序 8.三维数组R[c1„d1,c2„d2,c3„d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1） 9.数组A[1„10，-2„6，2„8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。10.913 三、简答题（每题6分，共18分）1.已知L是无表头结点的单链表，且P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1)在P结点后插入S结点。(2)在表首插入S结点。(3)在表尾插入S结点。2已知L是带表头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1)删除P结点的直接后继结点。(2)删除P结点。（3）删除尾元结点。3． LinkList mynote(LinkList L){//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next)p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2, „,an）,写出算法执行后的返回值所表示的线性表。 该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 四、算法设计题（每题14分，共42分）1.假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知p为指向链表中某结点的指针，设计在链表中删除p所指结点的前趋结点的算法。 解：可引入一个指针q，当q->next=p时，说明此时q所指的结点为p所指结点的前趋结点，从而可得算法如下： void delete(LinkList *p){ //在链表中删除p所指结点的前趋结点 LinkList *q,*t; q=p; while(q->next->next!=p)//q->next不是p的前趋结点 （第2页，共3页） q=q->next; t=q->next;//t指向要删除结点 q->next=p;//删除t结点 free(t);｝ 2.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。 2．算法描述如下： delete(LinkList *head, int max, int min){ LinkList *p,*q; q=head; p=head->next; while(p!=NULL) if((p->data<=min)||(p->data>=max)) { q=p; p=p->next; } else { q->next=p->next;free(p);p=q->next;} } 3.假设表达式有单字母变量和双目四则运算符构成。试写一个算法，对一个通常书写形式且书写正确的表达式求值。 （第3页，共3页） 数据结构试卷 （一）一、选择题（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分）设单链表以非递减有序排列，设计算法实现在单链表中删除值相同的多余结点。第二篇：数据结构期中试卷及答案
第三篇：数据结构期中考试试卷答案
第四篇：数据结构试卷(一)及答案
第五篇：广东海洋大学数据结构试卷及答案
点击咨询 