数据结构全真模拟试卷.docVIP

全真模拟试卷（1） 一、单项选择题 1、线性表是具有n个______的有限序列(n0)。 A．表元素B．字符C．数据元素D．数据项 2、栈和队列都是______。 A．顺序存储的线性结构B．链式存储的线性结构 C．限制存取点的线性结构D．限制存取点的非线性结构 3、若对n阶对称矩阵A以行序列为主序方式将其上三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1….(n(n+1))/2]中，则在B中确定aij(ij)的位置k的关系为______。 A．i×(i-1)/2+jB．j×(j-1)/2+iC．i×(i+1)/2+jD．j×(j+1)/2+i 4、树是以结点的分支定义______结构，表示数据元素之间______的关系。 ①网状②层次③一对多④多对多 A．①④B．②④C．②③D．①③ 5、一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足______。 A．其中任意一个节点均无左孩子 B．其中任意一个节点均无右孩子 C．其中只有一个叶结点 D．其中度为2的结点最多为一个 6、一个含有n个顶点和e条边得简单无向图，在其邻接矩阵存储结构中共有______个零元素。 A.e B.2e C.n2-e D.n2-2e 7、设网中的定点数为n，边的条数为e，则普里姆(Prim)最小生成树算法和克鲁斯卡尔(Kruskal)最小生成树算法的时间复杂度分别为______。 A．O(n2), O(n2) B．O(n2), O(eloge) C．O(n2), O(nlogn)D．O(nlogn), O(eloge) 8、用顺序查找方法查找长度为n的线性表时，在等概率情况下的平均查找长度为______。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 9、某类排序方法的稳定性是指______。 A．该算法不允许有相同的关键字记录B．该算法允许有相同的关键字记录 C．平均时间为O(nlogn)的排序方法D．以上都不对 10、一组记录的关键码为(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) 二、综合应用题 1、试设计一个实现下属要求的Locate运算函数。设有一个带头结点的双向链表L。每个节点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存储数据的成员data和访问频度freq，结点定义如下所示： Typedef struct Db1Node { DataType data; Int freq; Struct Db1Node *lLink; Struct Db1Node *rLink; } Db1Node; 所有结点的freq初始时都为0。每当在链表上进行一次Locate(L,x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频度访问的结点总是靠近表头。试利用C/C++实现满足上述要求的函数： Void Locate(Db1Node *first,DataType x)//first指向链表的头结点 2、已知先序遍历和中序遍历某棵二叉树的结点序列分别为ACKIJHLDBEGF和IKJCHLAEGBDF，请给出这棵二叉树。 全真模拟试卷（2） 一、单项选择题 1、对于顺序存储的线性表，其访问结点的时间复杂和插入、删除节点的时间复杂度分别____ A．O(n)O(n) B．O(n)O(1)C．O(1)O(n)D．O(1)O(1) 2.用单循环链表表示队列，下列说法中正确的是 ___。 A．必须设头指针和尾指针才能入队、出队都是方便 B．只设一个头指针，就可以入队、、出队都方便 C．只设一个尾指针，就可以入队、出队都方便 D．无论无何，上述3者方法都可能使入队方便 3.下列判断中吧，____是正确的。 A．二叉树就是度为2的树 B．二叉树中不存在度大于2的结点 C．二叉树是有序树 D．二叉树的每个结点的度都为2 4. 在平衡二叉树中，_____. A任意结点的左右子树结点数目相同 B任意结点的左右子树高度相同 C任意结点的左右子树高度之差的绝对值不大于1 D不存在度为1的结点 5无向图G=(V,E),其中V=|a,b,c,d,e,f,| E=|(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)|,对该图进行深度优先遍历，得到的顶点序列正确的是_____。 A．a,b,e,c,d,f