数据结构考试试题二及参考答案.doc

课程名称： 数据结构 考试时间： 姓名： 班级： 学号： 一、选择题（每题2分，共20分）（ ）1、 链表适用于_查找A) 顺序 B) 二分法 C) 顺序，也能二分法 D) 随机（ ）2、试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径 A) a,c,f,e,d,g,b B) a,c,e,f,d,g,b C) a,c,f,d,e,g,b D) a,c,f,d,e,b,g (有问题)（ ）3、栈中元素的进出原则是 A）先进先出 B）后进先出 C）栈空则进 D）栈满则出 （ ）4、已知图的邻接矩阵如下，根据算法思想，则从顶点0出发按广度优先遍历的结点序列是_。（有问题）A) 0 2 4 3 6 5 1 B)0 1 2 3 4 5 6 C) 0 4 2 3 1 5 6 D) 0 1 3 4 2 5 6（ ）5、用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是。 A）32 B）33 C）34 D）15（ ）6、给定二叉树的两种遍历序列，分别是：先序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，其后序遍历序列为： A) BHECGIFAD B) BHECIGADF C) BHECIGFAD D) CHEBIGADF（ ）7、有8个结点的无向图最多有 条边。 A）14 B）28 C）56 D）112（ ）8、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找 表中元素58，则它将依次与表中 比较大小，查找结果是失败。A）20，70，30，50 B）30，88，70，50 C）20，50 D）30，88，50（ ）9、一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为A）38, 40, 46, 56, 79, 84 B）40, 38, 46 , 79, 56, 84 C）40, 38，46, 56, 79, 84 D）40, 38, 46, 84, 56, 79（ ）10、排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为A）希尔排序 B）归并排序 C）插入排序 D）选择排序二、填空题（每空2分，共20分）1、在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点数可以有 。2、 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。3、设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 ，第二次出栈得到的元素是 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 ，第二次出队得到的元素是 。经操作后，最后在栈中或队中的元素还有 个。三、算法阅读理解题（每题10分，共30分）1、写出下列程序段的输出结果（栈的元素类型为char）。void main( )Stack S;/ Stack表示栈类型Char x,y;InitStack(S);/初始化栈X=c; y=k;Push(S,x);/ Push表示入栈操作Push(S,a); Push(S,y);Pop(S,x); / Pop表示出栈操作Push(S,t); Push(S,x);Pop(S,x); Push(S,s);while(!StackEmpty(S) Pop(S,y);printf(y);结点类型定义及算法如下：struct node char data; struct node *lchild, rchild;void traversal(struct node *root)if (root) printf(“%c”,root-data); traversal(root-lchild); printf(“%c”,root-data);traversal(root-rchild); Printf(x); 2、设如图一所示的二叉树BTREE的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，对二叉树BTREE，执行算法traversal(root)，试分析算法的作用并指出算法执行后的输出结果。 图一：二叉树BTREEAB D C F G E3、下面程序实现了对输入数据进行直接插入排序的过程，并输出排序后的结果请在_处给出所缺失的内容。typedef structInt key;int other_data;RecordType;void InsSort(RecordType r, int length)/* 对记录数组r做直接插入排序，length为数组中待排序记录的数目*/ int i,j;for (i=2; i=length; i+) （1） ; /*设置哨兵*/j=i-1; （2） ； /*寻找插入位置*/ rj+1= rj; j=j-1; （3） ; /*将待插入记录插入到已排序的序列中*/ void main()int i,j;RecordType r20;int len;printf(请输入待排序记录的长度:);scanf(%d,&len);for(i=1;i=len;i+)printf(请输入第%d个记录元素:,i);scanf(%d,&j); （4） ; /*将输入的数据保存到结构体中的数据域中*/for(i=1;i=len;i+)printf(%d ,ri.key);printf(n);InsSort(r,len);for(i=1;i=len;i+)printf(%d , （5） ); /*输出排序后的数据*/printf(n);四、算法设计题（每题15分，共30分）1、下面给出了单链表的结构体类型定义，请编写算法，由键盘输入一组数据，用尾插法建立一个单链表，并输出链表中的数据。编写算法时，给出算法的功能说明和一定数量的注释。typedef char ElemType;typedef struct Node /*结点类型定义*/ ElemType data;struct Node * next;Node, *LinkList; /* LinkList为结构指针类型*/2、编写冒泡排序算法，实现对键盘输入的一组数据进行排序并输出结果编写算法时，给出算法的功能说明和一定数量的注释。参 考 答 案一、选择题（每题2分，共20分）1、A ；2、B?；3、B；4、B；5、B；6、C；7、B；8、A；9、C；10、D。二、填空题（每空2分，共20分）1、前驱，1，后继，任意多个；2、队列；3、a2，a4，a1，a2，2； 三、算法阅读理解题（每题10，共30分）1、答：输出为“stack”。2、答：该算法实现对二叉树的中序遍历， 执行后得到中序序列：ABCCEEBADFFDGG3、1）r0=ri 2）while (r0.keynext=NULL;void CreateFromTail(LinkList L) Node *r, *s;char c;int flag =1; /*设置一个标志，初值为1，当输入$时，flag为0，建表结束*/r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/ void main()LinkList l;Node *p;init_linklist(&l);printf(用尾插法建立单链表,请输入链表数据,以$结束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;2、1）冒泡排序程序#include #include #define TRUE 1#define FALSE 0typedef int KeyType;typedef int OtherType;typedef structKeyType key;OtherType other_data;RecordType;void BubbleSort(RecordType r, int length )/*对记录数组r做冒泡排序，length为数组的长度*/int n,i,j;int change;RecordType x;n=length; change=TRUE;for ( i=1 ; i= n-1 & change ;+i ) change=FALSE;for ( j=1 ; j rj+1.key ) x= rj;rj= rj+1;rj+1= x;change=TRUE; /* BubbleSort */ void main()int i,j;RecordType r20;int len;pr