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

课程名称： 数据结构 考试时间： 姓名： 班级： 学号： 一、选择题（每题2分，共20分）（ ）1、二叉树是非线性数据结构，所以_。）顺序存储结构和链式存储结构都能存储;）它不能用链式存储结构存储; ）它不能用顺序存储结构存储;）顺序存储结构和链式存储结构都不能使用 （ ）2、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的， 称之为_。 A）随机存储结构 B）逻辑结构 C）顺序存储结构 D）链式存储结构（ ）3、判定一个栈ST（最多元素为m0）为空的条件是_。 A）ST-top0 B）ST-top=0 C）ST-topm0 D）ST-top=m0A0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 3 6 1 5 4 2D. 0 1 3 4 2 5 6（ ）4、已知图的邻接矩阵如下，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是_。（ ）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）56 B）28 C）14 D）112（ ）8、对22个记录的有序表作折半查找，当查找失败时，至少需要比 较_次关键字。 A）3 B）4 C）5 D）6（ ）9、对个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。）从小到大排列好的 ）从大到小排列好的 ）元素无序 ）元素基本有序（ ）10、下列排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_。 ） 希尔排序 ） 冒泡排序 ） 选择排序 ）插入排序二、填空题（每空2分，共20分）1、在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 后续结点，其余每个结点有且只有1个后续结点。2、线性表、栈和队列都是 结构，可以在线性表的 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 插入和 删除元素。3、设用一维数组A1,n来表示一个栈，An为栈底(注意!)，用整型变量T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值_；从栈中弹出（POP）一个元素时，变量T的值_。4、由个结点所构成的二叉树有_种形态。三、算法阅读理解题（每题10分，共30分）1、分析并写出下列程序段的输出结果（队列中的元素类型为char）。void main( )Queue Q; / Queue表示队列InitQueue (Q); Char x=e,y=c;EnQueue (Q,h); / EnQueue表示入队操作EnQueue (Q,r); EnQueue (Q, y); DeQueue (Q,x); / DeQueue表示出队操作EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);2、设如下图所示的二叉树BTREE的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型， 对二叉树BTREE，执行算法traversal(root)，试分析算法作用并指出算法执行后的输出结果。树的结点类型定义如下：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); A B D C F G E 3、下面程序实现了对输入数据进行直接插入排序的过程，并输出排序后的结果请在_处给出所缺失的内容。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、C；3、B；4、D；5、B；6、C；7、A；8、C；9、B；10、D。二、填空题（每空2分，共20分）1、没有、没有；2、线性、任何、栈顶、队首、队尾；3、减少一，增加一；4、5三、算法阅读理解题（每题10，共30分）1、答：输出为“char”。与答案“char”中的字符位置对应，并且字符正确，每写出一个正确的字符计2.5分。2、答：该算法是二叉树的先序和中序遍历合成算法，执行后得到先序序列：ABCCEEBADFFDGG与答案“ABCCEEBADFFDGG”中的字符位置对应，并且字符正确，按写出的正确字符分别计分，其中前八个字符每写正确一个计0.5分，后六个字符每写正确一个计1分。3、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;单链表初始化函数计3分，其中函数的格式计1分，生成链表计1分，链表初始化计1分；建立单链表函数计7分，其中函数的格式计2分，变量初始化计1分，建立链表计4分；主函数计5分，其中变量初始化计1分，调用单链表初始化函数计1分，调用建立链表函数计1分，输出单链表计2分。2、简单选择排序程序#include #include typedef int KeyType;typedef int OtherType;typedef structKeyType key;OtherType other_data;RecordType;void SelectSort(RecordType r, int length)/*对记录数组r做简单选择排序，length为数组的长度*/int i,j,k;int n;RecordType x; n=length;for ( i=1 ; i= n-1; +i) k=i;for ( j=i+1 ; j= n ; +j) if (rj.key rk.key ) k=j;if ( k!=i) x= ri; ri= rk;rk=x; /* SelectSort */ 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);ri.key = j;for(i=1;i=len;i+)prin