数据结构试卷

1、数据结构试卷及答案一、 选择题（每小题2分，共30分）1计算机识别、存储和加工处理的对象被统称为( )。A.数据 B.数据元素 C.数据结构 D.数据类型2栈和队列都是（ ）。A限制存取位置的线性结构 B顺序存储的线性结构C链式存储的线性结构 D限制存取位置的非线性结构 3链栈与顺序栈相比，比较明显的优点是( ) 。A.插入操作更加方便 B.删除操作更加方便C.不会出现下溢的情况 D.不会出现上溢的情况4采用两类不同存储结构的字符串可分别简称为( ) 。A.主串和子串 B.顺序串和链串C.目标串和模式串 D.变量串和常量串5 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元

2、素的地址是：（ ）。A. 110 B .108 C. 100 D. 120 6串是一种特殊的线性表，其特殊性体现在：（ ）。A.可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符7设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：（ ）。A. 2h B .2h-1 C. 2h+1 D. h+1 8树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ ( )。A. 树的先根遍历序列与其对应的二叉树的先序遍历序

3、列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9一个有n个顶点的无向图最多有多少边？（ ）。A. n B .n(n-1) C. n(n-1)/2 D. 2n10在一个图中，所有顶点的度数之和等于所有边数的多少倍? （ ）。A. 1/2 B .1 C. 2 D. 4 11当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ ）。A左子树的叶子结点 B左子树的分支结点C右子树的叶子结点 D右子树的分支结点12对于哈希函数H(key)=

4、key%13,被称为同义词的关键字是( )。A.35和41 B.23和39 C.15和44 D.25和5113、 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（ ）。 A.快速排序 B.希尔排序 C.冒泡排序 D.堆排序 14、对有18个元素的有序表做折半查找，则查找A3的比较序列的下标依次为（ ）。 A.1-2-3 B.9-5-2-3C.9-5-3 D. 9-4-2-3 15、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ ）。 A.堆排序 B.冒泡排序 C.快速排序 D.直接插入排序 二、判断题（每小题1分，共10分） 1.线性表的长度是线性表

5、所占用的存储空间的大小。 2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。 3.在对链队列做出队操作时，不会改变front指针的值。 4.如果两个串含有相同的字符，则说它们相等。 5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。 6.已知一棵树的先序序列和后序序列，一定能构造出该树。 7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。 8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。 9.对一个堆按层次遍历，不一定能得到一个有序序列。10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。三填空题（每题2分共20分）1有

6、向图的存储结构有（ ）、（ ）、（ ）等方法。2已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。其后序遍历次序为（ ）。层次遍历次序为（ ）。3设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址。已知A00的存储地址为100。则按行存储时，元素A14的第一个字节的地址是（ ）；按列存储时，元素A14的第一个字节的地址是（ ）。4请在下划线上填入适当的语句，完成以下法算。Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e) /先序非递归遍历二叉树Initstack ( S );

7、 Push ( S,T );While ( !stackempty( S ) ) While ( gettop( S, p )& p ) visit (p-data ) ; ; Pop ( S , p ); If ( !stackempty(s) ) ; ; return ok;四、应用题(每小题6分，共18分) 1.假定在学生的档案中含有：姓名、学号、年龄、性别。如采用线性表作为数据结构来实现档案管理问题，分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义。 2.有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为8、14、10、4、18，请构造相应的哈夫曼树(左

8、子树根结点的权小于等于右子树根结点的权)，求出每个字符的哈夫曼编码。 3.有初始的无序序列为98,65,38,40,12,51,100,77,26,88,给出对其进行归并排序(升序)的每一趟的结果。 五算法设计题（每小题11分，共22分）1. 单链表结点的类型定义如下：typedef struct LNode int data; struct LNode *next; LNode, *Linklist;写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。(注:不破坏A和B的原有结构.)2. 二叉树用二叉链表存储表示。typedef struct BiTNode TelemType da

9、ta; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree;编写一个复制一棵二叉树的递归算法。一、A A D B B B C A C C A D A C D二、三、1、邻接矩阵、邻接表、十字链表2、edcgbfa、afbcgde3、144、1844、push(S, p-lchild) pop(S, p) push( S, p-rchild )四、1.顺序实现： const maxsize=100; 顺序表的容量 type datatype=record 档案数据类型 namestring10;姓名 numberinteger;学号 sexbool

10、ean;性别 ageinteger;年龄 end; type slist =record dataarray 1.maxsize of datatype; lastinteger; end; 链接实现： type pointer=node; node=record namestring 10;姓名 numberinterger； 学号 sex boolean;性别 ageinteger;年龄 nextpointer;结点的后继指针 end; list=pointer; 2.哈夫曼树为： 相应的哈夫曼编码为： a:001 b:10 c:01 d:000 e:113.初始无序序列： 98 65 3

11、8 40 12 51 100 77 26 88 98 65 38 40 12 51 10077 2688第一次归并： 65 98 38 40 12 51 77 100 26 88第二次归并： 38 40 65 98 12 51 77 100 26 88第三次归并： 12 38 40 51 65 77 98 100 26 88第四次归并： 12 26 38 40 51 65 77 88 98 100五、Merge(Linklist A, Linklist B, Linklist &C )void Merge(Linklist A, Linklist B, Linklist &C) C=(Link

12、list)malloc(sizeof(LNode);pa=A-next; pb=B-next; pc=C;while(pa&pb) pc-next=(Linklist)malloc(sizeof(LNode);pc=pc-next;if(pa-datadata) pc-data=pa-data; pa=pa-next;else pc-data=pb-data; pb=pb-next;if(!pa) pa=pb;while(pa) pc-next=(Linklist)malloc(sizeof(LNode);pc=pc-next;pc-data=pa-data; pa=pa-next;pc-next=NULL;BiTree CopyTree(BiTree T) if (