计算机考研数据结构试卷十一(练习题含答案)

共25套适用于计算机考研数据结构系统练习

（PS：其他正在整理，敬请期待）

数据结构试卷11

一、填空:

1.设需要对5个不同的记录关键字进行排序，则至少需要比较

_____________次，至多需要比较_____________次。

2.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较

_________次。

3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数

有_________个，比较两次查找成功有结点数有_________个。

4.数据结构从逻辑上划分为三种基本类型：___________、__________和

___________。

5.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具

有n个顶点的有向完全图中，包含有________条边。

6.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比

原树的高度___________。

7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为

________，整个堆排序过程的时间复杂度为________。

8.在快速排序、堆排序、归并排序中，_________排序是稳定的。

9.在有n个叶子结点的哈夫曼树中，总结点数是_______。

10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉

链表BT中所对应的结点一定_______。

二、选择题：

1.队列的特点是【】。

A 先进后出

B 先进先出

C 任意位置进出

D 前面都不正确

2.有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行【】

遍分配与收集。

A n

B d

C r

D n - d

3.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺

序【】。

A 都不相同

B 完全相同

C 先序和中序相同，而与后序不同

D 中序和后序相同，而与先序不同

4.设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为

【】。

A 12

B 13

C 14

D 15

5.下面关于广义表的叙述中，不正确的是【】。

A 广义表可以是一个多层次的结构

B 广义表至少有一个元素

C 广义表可以被其他广义表所共享

D 广义表可以是一个递归表

6.设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度

完全二叉树各有f个结点和c个结点，下列关系式不正确的是【】。

A f>=c

B c>f

C f=2k+1-a

D c>s k-1

7.从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为【】。

A head(tail(L))

B head(head(tail(L)))

C tail(head(tail(L)))

D head(tail(head(tail(L))))

8.下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是【】。

A 顺序结构

B 链接结构

C 索引结构

D Hash结构

9.在数据结构中，数据元素可由【】。

A 实体

B 域

C 数据项

D 字段

10.对于有n个顶点的有向图，由弗洛伊德（FloyD 算法求每一对顶之间的最短

路径的时间复杂度是【】。

A O(1)

B O(n)

C O(n)

D O(n3)

三、计算与算法应用题：

1.已知一个图的顶点集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)1 8,(6,7)25};

按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。

2.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出

来。试求出空格处的内容，并画出该二叉树。

先序序列： B F ICEH G

中序序列：D KFIA EJC

后序序列：K FBHJ G A

四、阅读下列算法，分析它的作用：

1.int AA(LNode *HL , ElemType x)

{

int n=0;

LNode *p=HL;

while (p!=NULL)

{

if (p->data= =x) n++;

p=p->next;

}

return n;

}

对于结点类型为LNode的单链表，以上算法的功能为：

2.int AA(LNode *HL , ElemType x)

{

int n=0;

LNode *p=HL;

while (p!=NULL)

{

if (p->data= =x) n++;

p=p->next;

}

return n;

}

对于结点类型为LNode的单链表，以上算法的功能为：

五、算法设计题：

1.编写复制一棵二叉树的非递归算法。

2.假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，

试编写算法按如下图所示的树状显示二叉树。

答案（PS:后15套较难，有不会的可以@我）

一、填空题

1.4，10

2.n

3.1，2

4.线性结构，树型结构，图型结构

5.n(n-1)/2 n(n-1)

6.增加1

7.O(log2n) O(nlog2n)

8.归并

9.n-1

10.左右子树空

二、单项选择题

1---5 BBBCB

6---10 BDACD

三、计算与算法应用题

1.普里姆算法从顶点1出发得到最小生成树为：

(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20

2. 在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。

四、阅读下列算法，分析它的作用

1.统计单链表中结点的值等于给定值x的结点数。

2.对数组A中的n个元素进行排序，称为起泡算法。

五、算法设计题：

1.将算法实现函数声明为二叉树类的友元函数，可采用层次遍历的方式进行复制，将已复制的结点进入一个队列中即可。

具体算法实现如下：

// 文件路径名:exam5\alg.h

template

void CopyBitree(BinaryTree *fromBtPtr, BinaryTree *&toBtPtr)

// 操作结果: 复制二叉树fromBt到toBt的非递归算法

{

if (toBtPtr != NULL) delete toBtPtr; // 释放toBtPtr

if (fromBtPtr->Empty())

{ // 空二叉树

toBtPtr = NULL; // 空二叉树

}

else

{ // 非空二叉树

LinkQueue *> fromQ, toQ; // 队列

BinTreeNode *fromPtr, *toPtr, *fromRoot, *toRoot;

fromRoot = fromBtPtr->GetRoot(); // 取出fromBtPtr的根

toRoot = new BinTreeNode(fromRoot->data); // 复制根结点

fromQ.InQueue(fromRoot); toQ.InQueue(toRoot); // 入队

while (!fromQ.Empty())

{ // fromQ非空

fromQ.OutQueue(fromPtr); // 出队

toQ.OutQueue(toPtr); // 出队

if (fromPtr->leftChild != NULL)

{ // 左子树非空

toPtr->leftChild = new BinTreeNode(fromPtr->leftChild->data);

// 复制fromPtr左孩子

fromQ.InQueue(fromPtr->leftChild); toQ.InQueue(toPtr->leftChild); // 入队

}

if (fromPtr->rightChild != NULL)

{ // 右子树非空

toPtr->rightChild = new BinTreeNode(fromPtr->rightChild->data);

// 复制fromPtr左孩子

fromQ.InQueue(fromPtr->rightChild); toQ.InQueue(toPtr->rightChild); // 入队}

}

toBtPtr = new BinaryTree(toRoot); // 生成toBtPtr }

}

2.从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。具体算法实现如下：

// 文件路径名:exam1\alg.h

ss ElemType>

void DisplayHelp(BinTreeNode *r, int level)

// 操作结果：按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1

{

if(r != NULL)

{ // 空树不显式，只显式非空树

DisplayHelp(r->rightChild, level + 1); // 显示右子树

cout << endl; // 显示新行

for(int i = 0; i < level - 1; i++)

cout << " "; // 确保在第level列显示结点cout << r->data; // 显示结点

DisplayHelp(r->leftChild, level + 1); // 显示左子树

}

}

template

void Display(const BinaryTree &bt)

// 操作结果：树状形式显示二叉树

{

DisplayHelp(bt.GetRoot(), 1); // 树状显示以bt.GetRoot()为根的二叉树

cout << endl; // 换行

}

数据结构考研试卷 (10)

附录 B 三份数据结构考研试题及参考 答案 试题一(满分75) 一、单项选择题(2×10分,共20分) 1.某算法的时间复杂度为O(n2),表明该算法的＿. A.问题规模是n2 B.执行时间等于n2 C.执行时间与n2成正比 D.问题规模与n2成正比 2.设线性表有n个元素,以下操作中,＿在顺序表上实现比在链表上实现效率更高. A.输出第i(1≤i≤n)个元素值 B.交换第1个元素与第2个元素的值 C.顺序输出这n个元素的值 D.输出与给定值x相等的元素在线性表中的序号 3.设n个元素进栈序列是1,2,3,…,n,其输出序列是p1,p2,…p n,若p1=3,则p2的值＿. A.一定是2 B.一定是1 C.不可能是1 D.以上都不对 4.设循环队列中数组的下标是0～N-1,其头尾指针分别为f(指向队头元素的前一位置)和r(指向队尾元素的位置),则其元素个数为＿. A.r-f B.r-f-1 C.(r-f)%N+1 D.(r-f+N)%N 5.若串s=’abcefgh’,其子串(含空串和自身)的个数是＿. A.8 B.37 C.36 D.9 6.若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中,第一个非零元素a11存放于B[1]中,则应存放到B[k]中的非零元素a ij(1≤i≤n;1≤j≤i)的下标i，j 与k的对应关系是k=( )。 A.i(i+1)/2+j B. i(i-1)/2+j-1 C. j(j+1)/2+I D. j(j-1)/2+i-1 7. 设高度为h（根结点为第1层）的二叉树上只有度为0和度为2的结点，则此类二叉

树中所包含的结点数至少为( ). A. 2h B.2h-1 C.2h+1 D.h+1 8. 无向图的邻接矩阵是一个（ ）。 A. 对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵 9. 对线性表进行二分查找时，要求线性表必须（ ）。 A. 以顺序表方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键字有序排序 D. 以链式方式存储，且结点按关键字有序排序 10. 以下排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终位置上。 A. 快速排序 B.希尔排序 C.堆排序 D.冒泡排序 二、问答题（共30分） 1. 有5个字符，根据其使用频率设计对应的哈弗曼编码，以下哪些可能的哈弗曼编码。（8分） （1）000，001，010，011，1 （2）0000，0001，001，01，1 （3）000，001，01，10，11 （4）00，100，101，110，111 2. 一个有向图G 的邻接表存储如图B.1所示，现按深度优先搜索遍历，从顶点1出发，所得到的顶点时什么？（5分） v1 v2 v3 v4 ∧ v5 3. 已知一个有序表为（12，18，20，25，29，32，40，62，83，90，95，98），当二分查找值为29和90时，分别需要多少次比较才能查找成功？若采用顺序查找时，分别需要多少次比较才能查找成功？（8分） 4. 按13、24、37、90、53的次序形成二叉平衡树，回答以下问题：（9分） （1）该二叉平衡树的高度是多少？ （2）其根结点是谁？ （3）左子树中的数据是什么？ （4）右子树种的数据是什么？ 三=算法设计题（共25分） 设计一个算法int increase(LinkList * L),判定带头结点单链表L 是否是递减的，若是返回1，否则返回0.（10分） 假如二叉树采用二叉链存储结构存储，试设计一个算法，输出该二叉树种第一条最长的路径长度，并输出此路径上各结点的值。（15分） 试题一参考答案 2 3 3 ∧ 4 ∧ 5 ∧ 5 ∧ 4 1 2 3 4 5 图B. 1 一个有向图G 的邻接表

10年计算机考研真题解析

2010年全国硕士研究生入学统一考试 计算机学科专业基础综合试卷 一、单项选择题(1-40小题,每小题2分,共80分,下列每小题给出的四个选项中,只有一项符合题目要求,把所选项前的字母填在题后的括号内.) (1)若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是 (A)d,c,e,b,f,a(B)c,b,d,a,e,f(C)b,c,a,e,f,d(D)a,f,e,d,c,b (2)某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是 (A)b,a,c,d,e(B)d,b,a,c,e(C)d,b,c,a,e(D)e,c,b,a,d (3)下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是 (A)(B) (C)(D) (4)在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是 (A)13,48(B)24,48(C)24,53(D)24,90 (5)在一棵度数为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的 结点,10个度为1的结点,则树T的叶结点个数是

(A)41(B)82(C)113(D)122 (6)对n(n>=2)个权值均不相同的字符构成哈弗曼树,关于该树的叙述中,错误的是 (A)该树一定是一棵完全二叉树 (B)树中一定没有度为1的结点 (C)树中两个权值最小的结点一定是兄弟结点 (D)树中任一非叶结点的权值一定不小于下一层任一结点的权值 (7)若无向图G=(V,E)中含7个顶点,则保证图G在任何情况下都是连通的,则需要的边数最少是 (A)6(B)15(C)16(D)21 (8)对下图进行拓扑排序,可以得到不同的拓扑序列的个数是 (A)4(B)3(C)2(D)1 (9)已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在的元素,则比较次数最多的是 (A)4(B)5(C)6(D)7 (10)采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是 (A)递归次数于初始数据的排列次数无关 (B)每次划分后,先处理较长的分区可以减少递归次数 (C)每次划分后,先处理较短的分区可以减少递归次数 (D)递归次数与每次划分后得到的分区处理顺序无关 (11)对一组数据(2,12,16,88,5,10)进行排序,若前三趟排序结果如下: 第一趟:2,12,16,5,10,88 第二趟:2,12,5,10,16,88 第三趟:2,5,10,12,16,88 则采用的排序方法可能是 (A)冒泡排序法(B)希尔排序法(C)归并排序法(D)基数排序法 (12)下列选项中,能缩短程序执行时间的措施是 Ⅰ.提高CPU时钟频率 Ⅱ.优化通过数据结构 Ⅲ.优化通过程序 (A)仅Ⅰ和Ⅱ(B)仅Ⅰ和Ⅲ(C)仅Ⅱ和Ⅲ(D)Ⅰ、Ⅱ、Ⅲ (13)假定有4个整数用8位补码分别表示r1=FEH,r2=F2H,r3=90H,r4=F8H,若将运算结果存放在一个8位寄存器中,则下列运算会发生益处的是 (A)r1×r2(B)r2×r3(C)r1×r4(D)r2×r4 (14)假定变量i,f,d数据类型分别为int,float,double(int用补码表示,float和double用IEEE754单精度和双精度浮点数据格式表示),已知i=785,f=1.5678e3,d=1.5e100,若在32位机器中执行下列关系表达式,则结果为真的是

计算机考研数据结构试卷一(练习题含答案)

数据结构试卷1 一、单选题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放 位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚 注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中， 现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 n） D. O（n2） A. O（1） B. O（n） C. O（1og 2 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选 用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通 图。 A.5 B.6 C.7 D.8 二、填空题 1.通常从四个方面评价算法的质量：_________、_________、_________和 _________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含 的结点数为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应 的后缀算式为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩 子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针

计算机考研数据结构真题汇总

一.选择题篇 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1）它必须具备（2）这三个特性。【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n)

2019年考研《计算机数据结构》考试试题

2019年考研《计算机数据结构》考试试题 一、选择题(24分) 1.下列程序段的时间复杂度为( )。 i=0，s=0; while (s (A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2) 2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则 选用下列( )存储方式最节省运算时间。 (A) 单向链表(B) 单向循环链表 (C) 双向链表(D) 双向循环链表 3.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。 (A) s->next=p->next;p->next=-s; (B) q->next=s; s->next=p; (C) p->next=s->next;s->next=p; (D) p->next=s;s->next=q; 4.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 5.设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为( )。 (A) 10 (B) 19 (C) 28 (D) 55

6.设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有( )个叶子结点。 (A) (B) (C) (D) 7. 二叉排序树中左子树上所有结点的值均( )根结点的值。 (A) < (B) > (C) = (D) != 8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度 为( )。 (A) 129 (B) 219 (C) 189 (D) 229 9. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2 10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有( )个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 11.设一组初始记录关键字的长度为8，则最多经过( )趟插入排序可以得到有序序列。 (A) 6 (B) 7 (C) 8 (D) 9 12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是( )。 (A) F，H，C，D，P，A，M，Q，R，S，Y，X (B) P，A，C，S，Q，D，F，X，R，H，M，Y

2011年计算机统考真题+解析

王道考研系列 2011 年全国硕士研究生入学统一考试 计算机科学与技术学科联考计算机 学科专业基础综合 （科目代码：408） 特别鸣谢：阿三（casper08， 哈工大）王道考研系列辅导书 编写团队 予人玫瑰手留余香

2 2 共 1895个中间结点 一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一 项符合题目要求的。请在答题卡上将所选项的字母涂黑。) 1． 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是 x=2； while （x

计算机数据结构考研真题及其答案

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）; A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）; A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（），它必须具备（）这三个特性; (1)A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2)A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性4．一个算法应该是（）; A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C 5. 下面关于算法说法错误的是（）; A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）; (1）算法原地工作的含义是指不需要任何额外的辅助空间;（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法;（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界;（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类; A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）; A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）; A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关（）; A．栈 B. 哈希表 C. 线索树 D. 双向链表

南京大学计算机考研试题

2015南京大学计算机845考研试题 说明：本人在28号考试过程中抄下来的，时间有限有部分试题（13个选择/共40个，1个算法大题/大题共7个）遗漏，后又根据论坛和考研群其他研友的回忆版资料进行过补充，基本完全。其余因笔记仓促亦可能有少量笔误，见谅。望后来考生，应知年与时驰、意与日去，备考及早动手，坚持到底，衷心祝福大家都能学有所成，梦想成真。 感谢在我半年备考期间与我同一自习室复习的研友们，陈梅，王超，李玲，李浩，大白，王丽坤。感谢好友比助，姗姗，贝贝，成云，康师傅，丁小琳。感谢王道南大考研群诸位学长学姐和战友们，let，嘛嘛，木哥，Tomorrow，胸大的绿色兔子汪a（没错我就是在黑你），六月（强迫症死敌！），地下铁（真诚祝福兄弟），句号，皮卡丘，倩倩，唯安，沧海，浅月，绝，别情，夜吟，风之天炼，河北的妹子i（冒泡一次激励我三天加倍努力），亮靓（学妹加油），马克图布。仰头望明月，寄情千里光。愿你们拥有想要的未来，想去的远方。2014年12月30日于天津师范大学劝学楼C区503自习室。 作者：王道论坛章凝苏（1）单项选择题（40X2分） A.和动态链表相比，以下反映了静态链表缺点的是（） A.插入、输入输出操作不便 B.存储空间有时得不到充分利用 C.要求各结点有相同的类型 D.表中各结点只能读取不能修改

B.二维数组A[8][10]按列优先次序存储在起始地址为0的连续内存单元中，其中每个元素占5个单元，元素A[6，7]的存储地址是（） C.二叉线索树中执行较困难的运算是（） A.中序线索树下查找结点的前驱 B.中序线索树下查找结点的后继 C.前序线索树下查找结点的前驱 D.后序线索树下查找结点的前驱 D.设散列表为H[11]（下标从0开始）。将关键码序列（20，15，19，43，67，30）散列到该地址空间中，散列函数为H(key)=key%11，处理冲突采用线性探查法。则等概率情况下查找成功时平均搜索长度是（） A. B. C. D. 2 E.已知一颗二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，则后序遍历为（）A.CBEFDA B. FEDCBA C. CBEDFA D. 不确定 F.以下与数据的存储结构无关的术语是（） A.循环队列 B.链表 C.哈希表 D.优先级队列 G.具有n个关键字的有序表，采用监视哨方式查找，时间复杂度是（） (n) (n^2) (log以2为底n) (nlog以2为底n)

南京邮电大学2005年数据结构考研试卷

南 京 邮 电 学 院 2005年攻读硕士学位研究生入学考试 数 据 结 构 试 题 一、单选题（每题3分，共30分） 1. 设使用某算法对n 个元素进行处理，所需的时间是 T(n) = 100n log 2n + 200n + 2000 则该算法的渐进时间复杂度为 。 A. O(1) B. O(n) C. O(200n) D. O(nlog 2n) 2. 设顺序表的长度为n ，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是 。 A. (n －1)/2 B. n/2 C. n(n －1)/2 D. n(n ＋1)/2 3. 如果只保存一个n 阶对称矩阵a 的下三角元素（含对角线元素），并采用行主序存储在一维数组b 中，a[i][j]（或a[i, j]）存于b[k]，则对i

大数据结构考研真题及其问题详解

一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【理工大学 1999 一、1（2分）【交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（ D ）【理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D.栈

天津大学计算机技术专硕考研真题

天津大学计算机技术专硕考研真题 天津大学计算机技术专硕考研复习都是有依据可循的,考研学子关注事项流程为：考研报录比-大纲-参考书-资料-真题-复习经验-辅导-复试-导师，缺一不可。 首先笔者先简单地介绍一下自己的情况，笔者是2017届的考研党，报考的院校和专业是天津大学计算机技术专硕，本科是普通一本，是一个跨专业考生，很幸运地进入了复试阶段并且成为了天津大学的一员。最近正是开学季，也是大家开始要复习专业课的时候了，于是我决定把自己用过的真题资料书分享给大家，希望可以帮到考研的小伙伴们。 天津大学计算机技术专硕的专业课考试科目是901数据结构与程序设计，笔者用的真题资料书是：《天津大学901数据结构和程序设计考研红宝书》，由天津考研网主编。资料中包含了：天津大学901数据结构与程序设计1996－2007、2013、2014、2015、2016年考研真题；天津大学901数据结构与程序设计1996-2007、2013-2016年考研试题解析及参考答案；天津大学901数据结构与程序设计2000-2007、2013、2014年考研真题解析（是视频讲解课的形式）：“天津大学901数据结构与程序设计基础考研真题解析（答案+讲解视频）”，可直接搜索。下面是摘抄的部分真题： 天津大学901数据结构与程序设计2016年考研真题 今年901考试的难度不是很大，感觉上140应该问题不大，比去年稍微简单点，都不是很难，相当于acm初级水平。去年的编程题太简单，今年的编程题稍微提升了难度。然而实做题、读程序与写结束这些部分都是非常简单的，只要掌握好课本知识就没有任何问题，能快速解答。 901考试分为两个部分，就是名字中的这两个科目，其中数据结构考试题分为实做题和算法设计：C++分为程序填空，写结果+程序设计，程序设计要求输入输出可执行的完整的算法，这点与数据结构的算法设计不一样，那个只要表达清楚思想就可以了。本文运用复习课本是王道，数据结构综合联考单科，严蔚敏C语言版数据结构，谭浩强C++面向对象程序设计，这三本课本我感觉足以应付天大的901的考试了，里面有很多的考研类似题，值得大家借鉴。看这些课本的时候，我觉得应该注意，要保证你到考试的时候对数据的算法，每个算法是做什么的，它的特征，思路清晰，比如一说树的先序遍历，立刻想到递归的怎么写，非递归的怎么写，具体哪些算法需要记忆。C++编程，可以做一些ACM的简单题来练习。 数据结构实做题（共45分） 一、（10分）

数据结构考研试题精选及答案第1章绪论

绪论 一、选择题 1.算法的计算量的大小称为计算的( 复杂性 A.效率 B. 2. 算法的时间复杂度取决于 A.问题的规模 3. 计算机算法指的是( (1) A .计算方法 法 (2) A .可执行性、 B. 1), B. 4. 5. )。【北京邮电大学 2000二、3 (20/8 C. 现实性 D. 难度 、1 (2 分)] ( )【中科院计算所1998 待处理数据的初态 它必须具备( 排序方法 C. A 和 B 这三个特性。 C. 解决问题的步骤序列 D. 分) 】 调度方 可移植性、可扩充性 B. 可执行性、确定性、有穷性 易读性、稳定性、安全性 、1 ( 4 C.确定性、有穷性、稳定性 【南京理工大学 1999 一、1 (2分) 一个 算法应该是( )。【中山大学 A .程序 B .问题求解步骤的描述 下面关于算法说法错误的是( A. 算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D.以上几个都是错误的 下面说法错误的是( )【南京理工大学 2000 一、2 (1.5分)] (1 ) (2) (3) (4) A . D. 【武汉交通科技大学 1996 1998 二、1 (2 分)】 C .要满足五个基本特性 D . A 和C. 分) 】 )【南京理工大学2000 一、1 (1.5分)】 )【南京理工大学 2000 算法原地工作的含义是指不需要任何额外的辅助空间 在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度 O(2n )的算法 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 同一个算法，实现语言的级别越高，执行效率就越低 (1) B.(1),(2) 7.从逻辑上可以把数据结构分为 A.动态结构、静态结构 C.线性结构、非线性结构 &以下与数据的存储结构无关的术语是 A.循环队列 B. 链表 9.以下数据结构中，哪一个是线性结构 A.广义表 B. 二叉树 10 .以下那一个术语与数据的存储结构无关？ A.栈 B. 11 .在下面的程序段中， 分)] 6. C.(1) ,(4) D.(3) ( )两大类。【武汉交通科技大学 1996 一、4 ( 2分)] B .顺序结构、链式结构 .初等结构、构造型结构 )。【北方交通大学 2000二、1 (2分)] 哈希表 D. 栈 )?【北方交通大学 2001 一、1 (2分)] 稀疏矩阵 ) 线索树 C. C. 哈希表 C. 对 x 的赋值语句的频度为( D.串 【北方交通大学2001 一、2 (2分)】 D. 双向链表 )【北京工商大学 2001 一、10 (3 FOR i:=1 FOR j:=1 x:=x+1; A. O(2 n) TO TO DO DO .0(n) 2 C . O(n) D .O(log 2n ) 12.程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO

2016年东南大学935计算机专业基础考研真题(回忆版)【圣才出品】

2016年东南大学935计算机专业基础考研真题（回忆版） 2016年的题型跟14年的一样。 选择题类似2014年的，共40道选择题。其中操作系统16道，数据结构和组成原理均12道。数据结构和操作系统都是很基础的，计组稍微难一点，不过仔细复习注意联系还是都可以轻松地选出正确答案的。 操作系统 1．页表的题。（但是跟往年的差距很大） 一个计算机的逻辑地址空间有64个页，每个页的大小是2048B。物理地址空间占用32个页框（frame）。一个程序P占用6个页框，并且0到5号逻辑页分别分配到3，4，1，7，10，11号页框（具体数字不太确定，只确定最后两个）。 （1）P的逻辑地址有多少位 （2）该计算机的物理地址有多少位 （3）P运行时，逻辑地址为06045H和0C234H的物理地址分别是什么（这两个数字的具体是多少也不记得了，但是每个数字的前两位我确定是对的，而且都是5位16进制数）（4）若访问CPU的时间是200us，访问页表的时间是40us，命中率为90%，则有效访问时间是多少。（具体数字记不清了）

2．文件系统的题。（比较类似15年王道书上的237的第7题） 一个文件系统有10个索引块，每个磁盘块大小为2048B。 （1）若这10个索引块都是直接索引，则最大的文件是多大 （2）若有7个直接索引，2个一级间接索引，1个二级间接索引，最大的文件系统有多大 （3）若不用索引用FAT，FAT的大小已给。（具体想不起来数据了QAQ，反正这个题比较简单） 3．生产者消费者的题 有三个进程，一个进程往缓冲区里放数，缓冲区里面最多只能放n个数。另外两个进程，一个从缓冲区里取负数，另一个从缓冲区里取非负数。实现这三个进程的同步过程。 数据结构 1．想一个从10万个数里面选出最小的10个数的实现方法，不需要用算法实现，分析你的算法为什么高效。 2．一个数组，写一个算法找出这个数组中最大的逆序差。（逆序差就是i＜＝j的情况下，A[j]－A[i]的差。比如4 15 5 6 9 1 16 11中最大的逆序差就是16－1＝15） 计算机组成原理

天津大学数据结构和程序设计考研真题

天津大学数据结构和程序设计考研真题-考研资料-笔记讲义 许多学生在考研复习的时候，都会遇到重点不明确，不知道从何复习的情况。为此，天津考研网建议，考研复习中，专业的考研复习资料，是帮助考生能够快速掌握复习重点及方法必不可少的因素，然后就是真题和讲义，可以让同学了解历年考研的出题方向和大致范围。天津考研网推出了天津大学数据结构和程序设计的考研复习资料及真题解析班，以下为详细介绍: 天津大学数据结构和程序设计考研真题等资料由天津考研网签约的天津大学计算机科学与技术学院高分考研学生历时近一月所作，该考生在考研中取得了专业课129分的好成绩并在复试中更胜一筹，该资料包含该优秀本校考生的考研经验、考研试题解题思路分析、复试流程经验介绍以及针对官方指定参考书的重难要点并根据天津大学本科授课重点整理等，从漫漫初试长路到紧张复试亮剑为各位研友提供全程考研指导攻关。 特别说明：此科目06年以前科目名称为数据结构；自06年到08年科目名称改为计算机基础（包含数据结构、程序设计、计算机原理）；自09年开始全国统考，科目名称为计算机学科专业基础综合；自2013年开始由学校自主命题，科目名称改为901数据结构与程序设计。 第一部分由天津考研网提供的核心复习资料： 天津大学数据结构和程序设计资料编者序言：本文的重点在于C++，数据结构的复习和复试基本情况介绍。C++、数据结构又分别从复习规划，复习用书，重点知识点结合历年考题这四个方面来展开的。复习规划大家务必看一下，然后根据自己的实际情况在制定自己的复习时间，因为内容很多，大多数同学都在考试之前复习不完，在心理因素上就落了一节。重点知识点一定要看了，这些知识点几乎每年都会有题了。另外我还给了历年试题的答案供大家参考。有的答案是自己做的答案，可能会有疏忽的地方。望大家提出宝贵的意见和建议。复试的东西现在了解一下即可，等到进复试了，还是有足够的时间看的。另外我还给了些自己复习心得。考完后感慨很多，回顾了这多半年来自己的成败得失。希望大家从一开始就沿着比较高效的方向前进，减少不必要时间的浪费。本资料格式为A4纸打印版，总量达到了130页共计50000余字，清晰易复习，已于编写者签订资料保真转让协议，各位研友可放心使用参考！特别提示：本站尽力保证资料的有用性，但由于个人复习态度进度不同，故请酌情参考本资料！ 天津大学数据结构和程序设计考研真题等资料目录 一、学院专业综述 二、近年来的录取情况及分数线 三、05、06年专业课试题的变化及其今后的趋势 四、复习策略和复习时间的统筹安排及所需要的辅助资料 五、C++和数据结构复习规划及复习侧重点(特别是05，06年的变化) 5七、复习经验与教训(学习生活心理诸方面) 八、关于数学和政治复习的小小的建议 九、计算机复试 十、附言

2018计算机考研：计算机数据结构测试题(九)

2018计算机考研：计算机数据结构测试题(九) 2018考研，计算机专业课考试科目为：计算机组成原理、数据结构、操作系统以及计算机网络等，需要大家记忆的知识点有很多，但是不能死机硬背，还是要理解为主的，融会贯通才能把题做好，拿到高分，小编就为大家分享计算机数据结构测试题及参考答案，希望计算机考研的考生在复习之余能够认真做题，巩固知识。 计算机数据结构测试题(九) 一、选择题(24分) 1.下面关于线性表的叙述错误的是( )。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 3.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为( )。 (A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M

4.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为( )。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5.设某完全无向图中有n个顶点，则该完全无向图中有( )条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 6.设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。 (A) 9 (B) 10 (C) 11 (D) 12 7.设某有向图中有n个顶点，则该有向图对应的邻接表中有( )个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 8.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为( )。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8 二、填空题(24分) 1. 1. 为了能有效地应用HASH查找技术，必须解决的两个问题是 ____________________和__________________________。 2. 2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x)

考研资料数据结构试题汇总

第一章绪论 一、填空题（每空1分，共33分） 1. 一个计算机系统包括硬件系统和软件系统两大部分。 2. 一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。 3. 计算机软件可以分为系统软件和应用软件两大类。科学计算程序包属于应用软 件，诊断程序属于系统软件（工具）。 4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。 5. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 6. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 7. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 9. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 10．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 11. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 12. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 14. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 15. 一个算法的效率可分为时间效率和空间效率。 16. 任何一个C程序都由一个主函数和若干个被调用的其它函数组成。 二、单项选择题（每小题1分，共15分） （ B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII码B) BCD码C)二进制D)十六进制 （ D ）3. 软件与程序的区别是∶ A)程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 （ C ）4. 所谓“裸机”是指∶ A) 单片机B)单板机C) 不装备任何软件的计算机D) 只装备操作系统的计算机 （ D ）5. 应用软件是指∶ A)所有能够使用的软件B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件D) 专门为某一应用目的而编制的软件