长春理工计算机数据结构考研模拟整合版

1、一、选择题（共20分，每题1分）.从逻辑上可以把数据结构分为两大类，分别是（）。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D ,初等结构、构造型结构.下面给出的四种排序法中（）排序法是不稳定的排序法。A.插入 B. 冒泡 C.二路归并D. 堆排序.线性表是具有n个（）的有限序列（n0）。A.表元素 B .字符 C .数据元素D .数据项.在下面的程序段中，对x的赋值语句的频度为（）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+50;A. O（2n） B . O（n） C . O（n2）D . O（log J）.下述哪一条是顺序存储结构的优点

2、？（）A.存储密度大B .插入运算方便 C .删除运算方便 D .可方便地用于各种逻辑结构的存储表示.栈是一种（）的线性表。A.先进先出B.后进先出C.后进后出D.不分顺序.设栈的输入序列是1, 2, 3, 4,则（）不可能是其出栈序列。A. 4 , 3, 1, 2,B.2 , 1, 3, 4,C. 1,4, 3, 2, D. 1, 2, 4, 3,.双向链表中有两个指针域，llink 和rlink ,分别指回前驱及后继，设 p指向链表中的一 个结点，q指向一待插入结点，现要求在p前插入q,则正确的插入为（）p A .llink:=q; q 人.rlink:=p; p 人.llink 人.rl

3、ink:=q; qA.llink:=pA.llink;q A .llink:=pA.llink;p 人.llinkA.rlink:=q;q 人.rlink:=p;pA.llink:=qA.rlink;qA.rlink:=p; pA.rlink:=q; pA.llinkA.rlink:=q; qA.rlink:=p;pA.llinkA.rlink:=q; qA.rlink:=p; qA.llink:=pA.llink; pA.llink:=q;.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用 （）最节省时间。A.单链表 B.单循环链表C.带尾指针的单循环链表 D.带头结点的双循环链表

4、.树是结点的有限集合，一棵非空的树它有（）根结点。A.有0个或1个B.有0个或多个 C.有且只有一个D. 有1个或1个以上 TOC o 1-5 h z .设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为（）A.求子串 B .联接 C .求串长 D .匹配.已知串S= aaab,其Next数组值为（）。A 0123 B . 0012 C . 1231 D , 1211.设给定权值总数有 n个，其哈夫曼树的结点总数为（）A.不确定 B . 2n C , 2n+1 D . 2n-1.设森林F对应的二叉树为 B,它有m个结点，B的根为p,p的右子树结点个数为 n,森林 F中第一棵

5、树的结点个数是（）A. m-n B . m-n-1 C . n+1 D .条件不足，无法确定.深度为h的满m叉树的第k层有（）个结点。（1=k=h）A.箭-1B . mTC . m-1D . ni-1.树的后根遍历序列等同于t树对应的二叉树的（）.A.先序序列B.中序序列C. 后序序列 D. 没有对应关系.已知一棵二叉树的前序遍历结果为ABCDEF中序遍历结果为 CBAEDF则后序遍历的结果为（）。A. FEDCBA B . CBEFDA C . CBEDFA D ,不确定 TOC o 1-5 h z .在图的理论与应用中，关键路径是事件结点网络中（）。A.从源点到汇点的最长路径B .从源点到

6、汇点的最短路径C.最长回路D.最短回路.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A. 1/2 B . 2 C . 1D. 4.下列哪一种图的邻接矩阵是对称矩阵？（）A.有向图 B ,无向图 C . AOV网 D . AOER一、选择题（共20分，每题2分）.栈是一种（）的线性表。A.先进先出B.后进先出C. 后进后出 D.不分顺序.串的长度是指（）A.串中所含不同字母的个数B .串中所含字符的个数C.串中所含不同字符的个数D .串中所含非空格字符的个数.设S为一个长度为n的字符串，其中的字符各不相同，则 S中的互异的非平凡子串（非 空且不同于S本身）的个数为（）。A.

7、2n-1 B . n2 C . （n2/2）+（n/2） D . （n2/2）+（n/2）-1.从逻辑上可以把数据结构分为两大类，分别是（）。A.动态结构、静态结构B .顺序结构、链式结构C.线性结构、非线性结构D ,初等结构、构造型结构.下面给出的四种排序法中（）排序法是不稳定性排序法。A. 插入 B. 冒泡 C.二路归并D. 堆排序.设给定权值总数有n个，其哈夫曼树的结点总数为（）A.不确定 B . 2n C , 2n+1 D . 2n-1.设森林F对应的二叉树为 B,它有m个结点，B的根为p,p的右子树结点个数为 n,森林F 中第一棵树的结点个数是（）A. m-n B . m-n-1 C

8、 . n+1 D .条件不足，无法确定.数据序列（8, 9, 10, 4, 5, 6, 20, 1, 2）只能是下列排序算法中的（）的两趟排序后的结果。A.选择排序B.冒泡排序C.插入排序D. 堆排序.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。下列排序方法中，哪一个是稳定的排序方法？（）A.直接选择排序B .二分法插入排序C .希尔排序 D.快速排序.树是结点的有限集合，一棵非空的树它有（）根结点。A.有0个或1个B.有0个或多个 C.有且只有一个 D. 有1个或1个以上一、选择题（共20分，每题1分） TOC o 1-5 h z .

9、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。A. G中有弧B, G中有一条从 Vi至ij Vj的路径C. G中没有弧D. G中有一条从 Vj至ij Vi的路径.在一个无向图中，所有顶点的度数之和等于所有边数（）倍。A. 1/2 B. 2 C. 1 D. 4. n个顶点的强连通图中至少含有（）。A. n-1条有向边 B . n条有向边 C . n（n-1）/2 条有向边 D . n（n-1）条有 向边.在一棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个 数为（）A. 4 B . 5 C . 6 D . 7.图的逆邻接表存储结构只适

10、用于（）图A.有向 B .无向 C .森林 D .连通.若查找每个记录的概率均等，则在具有 n个记录的连续顺序文件中采用顺序查找法查找 一个记录，其平均查找长度人$1为（）。A. （n-1）/2 B. n/2 C. n D. （n+1）/2.下面关于二分查找的叙述正确的是（）。A.表必须有序，表可以顺序方式存储，也可以链表方式存储.表必须有序，而且只能从小到大排列C.表必须有序，且表只能以顺序方式存储D.表必须有序且表中数据必须是整型，实型或字符型.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A无左孩子的平衡因子为，右孩子的平衡因子为1,则应作()型调整以使其平衡。

11、A. LL B. LR C RL D RR.散列表的地址区间为 0-17,散列函数为H(K)=K mod17o采用线性探测法处理冲突，并将 关键字序列26, 25, 72, 38, 8, 18, 59依次存储到散列表中。存放元素59需要搜索的次 TOC o 1-5 h z 数是()。A. 2 B. 3C.4D.5.设要排序(Sort)的数据为：5, 1, 10, 2,15, 3,若采用堆排序法(Heap Sort )排为升序，则当堆树(Heap tree )第三次建成时，其树根节点数据内容是()。A. 3 B. 10C.15D.5.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为()

12、。A. O(1) B . O(log 2n)C . O(sqt(n) D . O(n).有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表 示该矩阵时，所需的字节数是()。A. 60 B . 66 C . 18000 D . 33.设给定权值总数有n个，其哈夫曼树的结点总数为()A.不确定 B . 2n C , 2n+1 D . 2n-1. 已知广义表：A=(a,b),B=(A,A),C=(a,(b,A),B), 求下列运算的结果：tail(head(tail(C)=()。A. (a) B . A C . a D . (A)15.设有一个8阶的对称矩阵 A,采用

13、以行优先的方式压缩存储。a11为第1个元素，其存储地址为1,每个元素占一个地址空间。试问元素a85的地址为()。A. 33 B . 30 C16.下面说法不正确的是()cA.广义表的表头总是一个广义表C.广义表难以用顺序存储结构13 D . 23B.广义表的表尾总是一个广义表D.广义表可以是一个多层次的结构17.在下述结论中，正确的是(只有一个结点的二叉树的度为0；二叉树的度为2;二叉树的左右子树可任意交换；深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A. B . C . D .对于有n个结点的二叉树，其高度为()A. nlog 2n B . log 2n C . |log 2

14、n|+1 D .不确定.设给定权值总数有 n个，其哈夫曼树的结点总数为()A.不确定B 2n.2n+1.2n-120.已知一棵二叉树的前序遍历结果为ABCDEF中序遍历结果为CBAEDF则后序遍历的结果A. CBEFDAB . FEDCBA C.CBEDFA、选择题（共20分，每题1分）1.线性表（a1,a2,an）以链接方式存储时,访问第 i位置元素的时间复杂性为（）。A. O (i ) B . O (1)C. O (n) D . O (i-1 )2.设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A. m-n B.m-n-1 C.n

15、+1 D.条件不足，无法确定3.非空的循环单链表 head的尾结点p满足（A. p.link=head B.p.link=NIL C.p=NIL D . p=head4. 一个长度为n的顺序存储的线性表中，向第i个元素（1 w i w n+1）位置插入一个新元素时,需要从后面向前依次后移（）个元素。A. n-in-i+1n-i-1 D5.在一个单链表中，若要在 p 个指针域的值。所指向的结点之后插入一个新结点，则需要相继修改（6.在一个带有头结点的双向循环链表中，若要在 向的结点，则需要对 q-next赋值为（）。p所指向的结点之后插入一个q指针所指A. p-prior B.p-next C.

16、p-next-next D.p-prior -prior7.由3个结点可以构造出多少种不同的二叉树?A2 B 3 C 48.关键路径是事件结点网络中（A.从源点到汇点的最长路径B.从源点到汇点的最短路径最长回最短回路. n个结点的完全有向图含有边的数目A. n*nB. n(n+ 1 )C.n /2D.n*.链栈与顺序栈相比，一个较为明显的优点是便利A.通常不会出现栈空的情形B.插入操作更加便利C.删除操作更加D.通常不会出现栈满的情形11.若已知一个栈的入栈序列是1,2,3,n,其输出序列为p1,p 2,p3,，pN,若pN是n,则pi 是（）。A. i Bn-i C . n-i+1.不确定.

17、最大容量为n的循环队列，队尾指针是rear ,队头是front ,则队空的条件是 （）。A. （rear+1） MO=front B . rear=front C . rear+1=front D . （rear-l）MODi=front.设有两个串p和q ，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。A.求子串 B .联接 C .匹配 D .求串长 TOC o 1-5 h z .下面关于串的的叙述中，哪一个是不正确的？（）。A.串是字符的有限序列B .空串是由空格构成的串C.模式匹配是串的一种重要运算D .串既可以采用顺序存储，也可以采用链式存储.已知串S= aaab , 其N

18、ext 数组值为（）。A. 0123 B . 1123 C . 1231 D , 1211.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）/12。A. 35 B. 37 C. 39 D. 43.数列（21,19, 37, 5, 2）经由冒泡排序法（bubble sort ）由小到大排序，在第一次执行交换（swap）的后所得结果为（）。A.（19 , 21 , 37,5,2）B. （21 , 19, 5, 37,2）C .（21 , 19, 37,2,5）D, （2, 21, 19, 37,5）.对于一个头指针为head的带头结点的

19、单链表，判定该表为空表的条件是（）。A. head=NULL B . headnext=NULL C . head next=head D . head!=NULL.在下列存储形式中，哪一个不是树的存储形式？（）A.双亲表示法B .孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法.已知一棵二叉树的前序遍历结果为ABCDEF中序遍历结果为 CBAEDF则后序遍历的结果为（）。A. CBEFDA B . FEDCBA C . CBEDFA D ,不定二、填空题（共 30分，每空2分）. 一棵具有n个结点的完全二叉树的树高度（深度）是 （1）。.数据结构分别为逻辑结构、存储结构（物理结构），逻辑结

20、构有分为四类基本结构，分别是（2）、（3）、（4）、（5）。存储结构（物理结构）又分为（6）存储结构和（7）存储结构。逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成结构和工9上结构。.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（10） 4.树是结点的有限集合，树是由根结点和若干颗子树构成的。一个节点含有的子树的个数称为该节点（11）; 一棵树高为K的完全二叉树至少有（12）个结点:高度为 K的二叉树最 大的结点数为（13）。5.霍夫曼树是一种带权路径最(14)的树,在一个度为 m的霍夫曼树中，其叶结点个数为n,则非叶结点的个数为(15)。二、填空题

21、(共 20分，每空2分).树是结点的有限集合，树是由根结点和若干颗子树构成的。树中含有的最大的子树的个数称为(1)； 一棵树高为K的完全二叉树至少有(2)个结点；高度为 K的二叉树最大的结 点数为(3)。.二叉树由(4), (4), (6)三个基本单元组成。.空格串是指CZ)，其长度等于(8)。. 一棵具有n个结点的完全二叉树的树高度(深度)是(9)。.在排序算法中，每次从未排序的记录中挑出最小(或最大)关键码字的记录，加入到已排序记录的末尾，该排序方法是(10)二、填空题(共 30分，每空2分)一个循环队列的最大容量为m Cq_front为队首指针，Cq_rear为队尾指针。那么进队操作时求

22、队位 Cq_rear = (1)。一棵二叉机推I度为h,所有结点的度或为 0,或为2,则这棵二叉树最少有(2)个结点对一组数据(84, 47, 25, 15, 21)排序，数据的排列次序在排序的过程中的变化为(1) 84 47 25 15 21(2) 15 47 25 84 21(3) 15 21 25 84 47(4) 15 21 2547 84则采用的排序是(3)排序。.树是结点的有限集合，树是由根结点和若干颗子树构成的。一个节点含有的子树的个数称为该节点(4); 一棵树高为K的完全二叉树至少有(5)个结点;高度为 K的二叉树最大 的结点数为(6)。.二叉树中某一结点左子树的深度减去右子树

23、的深度称为该结点的(7 )。.具有256个结点的完全二叉树的深度为(8 )。.就希尔排序的稳定性而言，是一种(9 )的排序方法。.字符串ababaabab的nextval为(10 )(答案数值用逗号隔开，勿添加空格和括号)。.数据结构分别为逻辑结构、存储结构(物理结构)，逻辑结构有分为四类基本结构，分别是(11)、(12)、(13)、(14)。.去除广义表LS=(a1,a2,a3,，an)中第1个元素，由其余元素构成的广义表称为LS的(15 )。二、填空题(共 30分，每空2分).通常从四个方面评价算法的质量：(1 )、 ( 2 ) 、 ( 3 )和(4 ) _。. 一个算法的时间复杂度为 (

24、n3+n210g2n+14n)/n2 ,其数量级表示为_ ( 5 )。.假定一棵树的广义表表示为A (C, D (E, F, G) , H (I , J),则树中所含的结点数为 ( 6 )个，树的深度为 ( 5 ),树的度为 ( 6 )。.后缀算式9 2 3 +- 10 2 / - 的值为（7 ）。中缀算式（3+4X） -2Y/3对应的后缀 算式为（8 ） _。.二叉树中某一结点左子树的深度减去右子树的深度称为该结点的（9 ）。.具有256个结点的完全二叉树的深度为（10 ）。.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共

25、有（11 ）。个指针域，其中有（12 ）。个指 针域是存放了地址，有（13 ）个指针是空指针。.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有（14 ）个和 （ 15 ）个。三、简答题（共60分）915 *1. （5分）如图1所示的二叉树，请分别写出中序和后序遍历序列。12图1第一题图图2第二题图. （5分）对于图2所示的无向带权图，构造最小生成树。（8分）什么是拓扑排序？简述 AOV网的含义。（ 8分）有一份电文中共使用 6个字符：a,b,c,d,e,f,它们的出现频率依次为 2,3,4,7,8,9 ,试构造一棵哈夫曼树，并1t算其加权路径长度WPL（8分

26、）（1）.如果G1是一个具有n个顶点的连通无向图，那么 G1最多有多少条边？G1最少有多少条边？（2）.如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？ G2最少有多少条边？（8分）关键字序列 T=（21 , 25, 49, 25* , 16, 08）,请写出一趟快速排序的结果。该排 序方法是稳定的吗？为什么？（8分）简述关键路径的求解步骤。（10 分）已知关键字集合 19, 01,23, 14, 55, 68, 11,82, 36 ，设定哈希函数 H（key） = key MOD 11 ,请构造哈希表，利用线性探测再散列di = c i ,其中c=1解决冲突，并计算平均查找

27、长度ASL。三、简答题（60分）（5分）栈是一种后进先出的线性表，如果一个栈的输入序列为1 , 2, 3请写出所有可 能的出栈序列。（5分）按照广义表的定义，已知已知广义表LS= （a,b,c）,（d,e,f）, 请写出运用head和tail函数取出LS中原子e的运算。（5分）设单链表结点指针域为next ,试写出删除链表中指针 p所指结点的直接后继的CtH 日 句 （10分）关键字序列 T= （21, 25, 49, 25*, 16, 08）,请写出直接插入排序的具体实现 过程。（10分）线性表有两种存储结构：一是顺序表，二是链表。试问：如果有 n个线性表同 时并存，并且在处理过程中各表的长

28、度会动态变化，线性表的总数也会自动地改变。 在此情况下，应选用哪种存储结构？为什么？（10分）简述起冒泡排序的基本思路及优点。（10分）如图所示，将下图的森林转换到二叉树，分别写出二叉树的前序和中序遍历序列。图1第7题图（ 10分）证明二叉树的性质，任一二叉树，若叶结点数是n0 ,度为2的结点数是n2，则n0=n2 +1（10分）如图1所示，树的存储结构可以有双亲法，孩子表示法等，请分别画出双亲法和带双亲的孩子表示法对该树的存储示意图。图2第9题图三、简答题（共60分）（5分）如图1所示的二叉树，请分别写出前序和中序遍历序列。图1第一题图图2第二题图. （5分）对于图2所示的无向带权图，构造最

29、小生成树。（8分）关键字序列 T=（20, 25, 49, 49* , 13, 05）,请写出快速排序的结果。该排序方 法是稳定的吗？为什么？（8分）根据给定集合15,3,14,2,6,9,16,17）,构造相应的huffman树，给出计算它的带权路径长度，以及集合中每个元素对应的huffman编码。（8分）简述线性结构与非线性结构的不同点。（8分）给出一组关键字 T=（12,2,16,30,8,28,4,10,20,6,18）,写出用希尔排序（第一趟排序的 增量为5）从小到大排序时第一趟结束时的序列。（8分）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线 性表中的元素

30、，那么应采用哪种存储结构？为什么？（10 分）已知关键字集合 19, 01,23, 14, 55, 68, 11,82, 36 ），设定哈希函数 H（key） = key MOD 11 ,请构造哈希表，利用线性探测再散列di = c i ,其中c=1解决冲突，并计算平均查找长度ASL。三、简答题（共60分）（5分）画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。（5分）如图1所示的二叉树，请分别写出前序和中序遍历序列。图1第一题图(10分)已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7);E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25); 用克 鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。(10分)阅读算法1. LinkList mynote(LinkList L)/L是不带头结点的单链表的头指针if(L&L-next)q=L ; L=L next; p=L ;S1:while(p next) p=p next;S2：pnext=q ; q next=NULL