数据结构试卷（八）参考答案
一、选择题 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; } }
数据结构试卷（九）参考答案
一、选择题
26
1．A 2．A 3．A 4．C 5．D 6．D 7．C 8．B 9．C 10．A 11．C 12．C 13．D 14．A 15．A 二、填空题
1. p->next，s->data 2. 50 3. m-1 4. 6，8 5. 快速，堆 6. 19/7 7. CBDA 8. 6
9. (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 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); } 数据结构试卷（十）参考答案 一、选择题 1．A 2．D 7．A 8．D 3．B 9．D 4．B 10．C 5．B 11．B 6．D 12．D 27 二、填空题 1. 4，10 2. O(nlog2n)，O(n2) 3. n 4. 1，2 5. n(m-1)+1 6. q->next 7. 线性结构，树型结构，图型结构 8. O(n2)， O(n+e) 9. 8/3 10. (38，13，27，10，65，76，97) 11. (10，13，27，76，65，97，38) 12. 124653 13. struct node *rchild，bt=0，createbitree(bt->lchild) 14. lklist，q=p 三、算法设计题 1. 设计在链式存储结构上合并排序的算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data 2. 设计在二叉排序树上查找结点X的算法。 bitree *bstsearch1(bitree *t, int key) { bitree *p=t; while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild; return(0); } 3. 设关键字序列(k1，k2，?，kn-1)是堆，设计算法将关键字序列(k1，k2，?，kn-1，x)调整为堆。 void adjustheap(int r[ ],int n) { int j=n,i=j/2,temp=r[j-1]; while (i>=1) if (temp>=r[i-1])break; else{r[j-1]=r[i-1]; j=i; i=i/2;} r[j-1]=temp; } 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（ ）是具有相同特性数据元素的集合，是数据的子集。 28 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是 ( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（ ）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（ ）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a85地址为（ ）。 A.23 B.33 C.18 D. 40 8．已知广义表 LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（ ）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) 。 A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。 A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构 D.随机表 链式存储结构 13．就平均查找速度而言，下列几种查找速度从慢至快的关系是（ ） A.顺序 折半 哈希 分块 B.顺序 分块 折半哈希 C.分块 折半 哈希 顺序 D.顺序 哈希 分块 折半 14．执行下面程序段时，执行S语句的次数为（ ） for(int I=1;I<=n;I++) for(int j=1;j<=I;j++) 29 S; A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 15．串是一种特殊的线性表，其特殊性体现在（ ） A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 16．树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论( )是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对 17．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为( )。 A. 60 B. 66 C. 67 D. 50 18．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( )个 A. 33 B. 34 C. 32 D. 30 19．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时，（ ）次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 20．若有文件的关键字序列为：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]，以下为二路归并排序过程。第二趟为: A.[265 301] [129 751] [863 937] [694 742] [076 438] B.[076 129 265 301 438 694 742 751 863 937] C.[129 265 301 694 742 751 863 937] [076 438] D.[129 265 301 751] [694 742 863 937] [076 438] 二、填空题（本大题共6小题，每空2分，共12分；答案填在下表内） 1 算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特 性，它们分别是 _______ 、______ 、________ 、有零或多个输入和有一或多个输出。 2 算法优劣的五个标准是正确性、可使用性、______、______、_____。 3 有n个球队参加的足球联赛按主客场制进行比赛，共需进行_________场比赛。 4 设有串t='I am a student '，s='good'，那么Concat(t,s)= 'I am a student good'，Substr(t,8,7)= __________。 5 在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个_________ 结构，其主要特点是__________。 6 广义表((a),a)的表头是_______，表尾是_______。 三、判断题（对的打“√”，错的打“×”。每小题1分，共10分;答案填在下表内） 1数据的逻辑结构与数据元素本身的内容和形式无关 。 30