下载文档原格式
数据结构试卷（一）一、单选题（每题2 分，共20分）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．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
数据结构试卷（一）一、单选题（每题2 分，共20分）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．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
一、（本题10分）栈与队列的区别和共同点是什么？队列主要有哪两种物理实现？ 答：区别：栈在表尾进行插入和删除，具有“后进先出”的特点；队列在表尾插入，在表头删除，具有“先进先出”的特点；共同点：栈和队列都是特殊的线性表，都是n 个数据元素的有限序列，都是数据结构的逻辑结构。
队列的物理实现：链队列和循环队列。
二、（本题10分）给出二叉树的定义，并画出具有3个结点的二叉树的所有形态。
答：所谓二叉树或者是空树，或者是如下定义的树：每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能颠倒。
3个结点的二叉树的所有形态如下：三、(本题15分)考虑下图：1) 从顶点A 出发，求它的深度优先生成树(字母小的优先访问)。
2) 从顶点E 出发，求它的广度优先生成树(字母小的优先访问)。
3) 使用克鲁斯卡尔算法，求它的最小生成树（给出树的生成过程）。
答：深度优先生成树为:广度优先生成树为:最小生成树为：（因为有相同的权值，树的生成过程可能不相同）评分标准：每小题5分。
四、（本题15分）假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)，哈希地址空间为0～12，若采用除留余数法H(K)=K % 13构造哈希函数，并使用链地址法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。
解：元素 哈希地址 查找次数平均查找长度为（1*8+2*2）/10=1.2评分标准： 画出哈希表得10分，平均查找长度得5分。
五、（本题15分）已知键值序列为｛45,56,83,31,72,35,14,47,89,19｝，要求给出：（1） 按键值排列次序构造一棵二叉排序树。
（2） 在等概率的情况下，该二叉排序树查找成功的平均查找长度。
（3） 针对上述10个键值，在不同的排列次序下所构造出的不同形态的二叉排序树中，在最坏和最好情况下，二叉排序树的高度各是多少？解：总分为15分，每一小步5分。
（1）（2）在等概率情况下，该二叉排序树的平均检索长度是：ASL=(1+2*2+3*4+4*3)/10=29/10=2.9（3）对于上述10个键值，在最坏情况下，每个结点（除了叶子结点）只有右孩子（或者只有左孩子），高度为10。
课程：数据结构专业：计算机科学与技术、网络工程、软件工程参考答案及评分标准一、单项选择题(10小题，每小题1分，共10分)1．算法指的是____D_____。
A．数据处理B．计算机程序C．解决问题的计算方法D．对特定问题求解步骤的一种描述，是指令的有限序列2．已知已个AOV网如图所示，下列____C_____不是该图的拓扑序列。
A．v0 v1 v5 v2 v3 v6 v4 B．v0 v1 v5 v2 v6 v3 v4C．v0 v1 v5 v3 v2 v6 v4 D．v0 v1 v5 v6 v2 v3 v43．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是___B______。
A．2 B．3 C．4 D．64．如果结点A有3个兄弟，B是A的双亲，则结点B的度是______D______。
A．1 B．2 C．3 D．45．二叉树的前序序列和后序序列正好相反，则该二叉树一定是___B______的二叉树。
A．完全二叉树B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子6．在一个无向图中，所有顶点的度数之和等于所有边数的____B______倍。
A．1 B．2 C．3 D．47．判定有向图是否存在回路除了可以利用拓扑排序方法外，还可以用_____A______。
A．深度优先遍历算法B．广度优先遍历算法C．求关键路径方法D．求最短路径方法8．下述排序方法中，比较次数与待排序记录的初始状态无关的是____C_______。
A．插入排序和快速排序B．归并排序和快速排序C．选择排序和归并排序D．插入排序和归并排序9．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值____A_____。
A．不一定都是同义词B．一定都是同义词C．一定都不是同义词D．都相同10．下列序列中，_______ 是执行第一趟快速排序的结果。
09级计科本科数据结构A卷2010 — 2011 学年度（第一学期）2009级计算机科学与技术专业《数据结构》本科期末试卷（A ）第 1 页共 2 页1. 计算机内部数据处理的基本单位是（）。
A.数据 B.数据元素 C.数据项D.数据库2. 设有一个递归算法如下 int fact(int n) { //n 大于等于0 if(n<=0) return 1; else return n*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）次。
A ．nB ．n+1C ．n+2D ．n-13. 在具有n 个单元的顺序存储的循环队列中，假定front 和rear 分别为队头指针和队尾指针，则判断队满的条件为( )。
A ．rear ％n= = frontB ．（front+l ）％n= = rearC ．rear ％n -1= = frontD ．(rear+l)％n= = front4. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列( )。
A ．A, B, C, D, E B ．B, C, D, E, A C ．E, A, B, C, DD ．E, D, C, B, A5. 若REPLACE （S ，S1，S2）表示用字符串S2替换字符串S 中的子串S1的操作，则对于S=“Beijing ＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE （S ，S1，S2）=（）。
A. “Nanjing ＆Shangha i”B. “Nanjing ＆Nanjing”C. “ShanghaiNanjing”D. “Shanghai ＆Nanjing” 6. 若数组A[0…m][0…n]按列优先顺序存储，则a ij 地址为（）。
A.LOC(a 00)+[j*m+i]B. LOC(a 00)+[j*n+i]C.LOC(a 00)+[(j-1)*n+i-1]D. LOC(a 00)+[(j-1)*m+i-1]7. 广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（）。
数据结构模拟试卷(一)及参考答案一．单项选择题（本大题共15小题，每小题2分，共30分）1．如果只想得到1024个元素组成的序列中的前5个最小元素，那么用( A )方法最快。
A、起泡排序B、快速排序C、堆排序D、直接选择排序2．算法分析的目的是（B）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（C）A．插入B．删除C．定位D．排序4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（D）A．3，2，6，1，4，5 B．5，6，4，2，3，1C．1，2，5，3，4，6 D．3，4，2，1，6，55．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（A）A．15 B．16C．17 D．186．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（B）。
A. 108B. 112C. 116D. 1207．从一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（C）个结点。
A. nB. n/2C. (n+1)/2D. (n-1)/28．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（D）A．不一定相同 B．互为逆序C．都不相同D．都相同9．高度为5的二叉树至多有结点数为（A）A. 63B. 32C. 24D.6410．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（B）A．图中每个顶点的出度B．图中每个顶点的入度C．图中弧的条数D．图中连通分量的数目11．图的邻接矩阵表示法适用于表示（C）A．无向图B．有向图C．稠密图D．稀疏图12．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则执行（D）。
数据结构试卷一、填空殖(每空1分共20分)1.数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情况。
2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___；若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域。
3.设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。
4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。
5.设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。
6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。
7.__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。
8.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。
9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。
10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。
11.设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为___________________________。
12.设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。
《数据结构》课程期末考试试卷（ A 卷）考核方式：开卷考试日期：2009 年1 月15 日适用专业、班级：08电子商务1、2一、填空题（每空1分，共10分）1．_字节是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
2．数据的物理存储结构分为____顺序存储结构____和____链式存储结构______二种。
3．下面程序段的时间复杂度是O（n）_____。
int n=10,sum=0;for(int i=0;i<n;i++)sum+=n;4.栈和队列是操作受限的线性表，队列又称_先进先出_______线性表。
5．若某完全二叉树的高度为h，则该完全二叉树中至少有______个结点，最多有______个结点。
6．每次使两个相邻的有序表合并成一个有序表的排序方法叫做归并排序。
7．在线性表的散列存储中，处理冲突的常用方法有__开放地址法_____________和_______链地址法_________两种。
二、综合运算题（每小题5分，共25分）1．有以下双端链表的图形，要求完成在最后一个结点插入一个新结点的语句，新插入结点为newEntry，其中newEntry中的数据元素值为“kate”。
其中节点定义类型如下：class Entry{Object data;Entry next;public Entry(Object data){this.data = data;}}2．已知一棵二叉树的前序遍历结果为ABDGEFCH，中序遍历的结果为GDBEAFHC，画出该二叉树，并给出后序遍历的结果。
3．将关键码6３，8８，7５，2７，9７，1９，9１，5５，3３依次插入到一棵初始为空的二叉搜索树中，画出对应的二叉搜索树。
4．举例说明clone方法的含义，并对浅克隆与深度克隆进行说明及图示？5．设待排序文件的关键码为（42, 65,80,77,43,55, 2,87,44,60），第一个元素为分界元素（枢轴）进行快速排序（按关键码值递增顺序），请给出第一趟排序后的结果。
1 河南农业大学2008—2009学年第一学期 《算法与数据结构》考试试卷（A卷）
题号 一 二 三 四 总分 分数
得分 评卷人 一、判断题（每题1分，共10分） 1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （ ） 2. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 3. 线性表的逻辑顺序与存储顺序总是一致的。（ ） 4. 栈和链表是两种不同的数据结构。（ ） 5. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。（ ） 6. 二叉树中每个结点有两棵非空子树或有两棵空子树。（ ） 7. 数据元素是组成数据的基本单位。（ ） 8. 对于一棵二叉树，它的根结点作为第一层，则它的第i层上最多能有 2i—1个结点。（ ） 9. 线性结构的链式存储结构是一种顺序存取的存储结构。（ ） 10.二叉树的中序遍历序列中，任意一个结点均处在其子女结点的前面。（ ） 学 院 课头号 班 级
姓名
学号
………………………………………………密………………………线………………………
…
…………………… 2
得分 评卷人 二、选择题（每题2分，共20分） 1.非线性结构是数据元素之间存在一种 。 A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系 2.算法分析的两个主要方面是 。 A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 3.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 A）110 B）108 C）100 D）120 4.具有n(n>0)个结点的完全二叉树的深度为 。 A) log2(n) B) log2(n) C) log2(n) +1 D) log2(n)+1 5.在一个图中，所有顶点的度数之和等于图的边数的 倍。 A）1/2 B） 1 C） 2 D） 4 6.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。 A）20，70，30，50 B）30，88，70，50 C）20，50 D）30，88，50 7．把一棵树转换为二叉树后，这棵二叉树的形态是 。 A）唯一的 B）有多种 C）有多种，但根结点都没有左孩子 D）有多种，但根结点都没有右孩子 8.有8个结点的无向连通图最少有 条边。 A)5 B) 6 C) 7 D) 8 9.最小生成树指的是（ ） A）由连通图所得到的边数最少的生成树 B）由连通图所得到的顶点相对较少的生成树 C）连通图的所有生成树中权值之和最小的生成树 D）连通图的极小连同子图 3
10.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ） A）n B） (n-1)2 C) n-1 D) n2
得分 评卷人 三、填空题（每空1分，共20分） 1. 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。 2. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点。 3. 一个字符串相等的充要条件是 和 。 4. 对于一棵具有n个结点的树，该树中所有结点的度数之和为 。 5．算法是指为解决给定问题而施行的有穷操作过程的描述。通常一个算法具备有五个特性，它们是它们是正确性、 、 、输入和 。 6．队列是只允许在表的 进行插入操作，而在 进行删除操作的线性表，栈是限定仅在 进行插入或删除操作的线性表。 7．在程序段 for(i=1;i<=n;i++) a=a+1; 中，时间复杂度为 。 8．希尔排序法是 稳定的内部排序方法。 9. 具有20个结点的完全二叉树的深度为 。 10.循环队列用数组A[m]存放起元素值，已知其头尾指针分别是front和rear则当前队列中元素的个数是 。 11.试举出两种常用的查找方法 ， 。
学 院
课头号 班 级 姓名 学号 ………………………………………………密………………………线………………………
…
…………………… 4 四、应用题（50分） 1. 给定一棵二叉树的两种遍历序列，分别是： 中序：C B E D A F I G H 后序：C E D B I F H G A (1) 构造出该二叉树（5分） (2) 画出该二叉树的后序线索化（5分）
2.已知如图所示的有向图，请给出该图的: （1） 每个顶点的入/出度；（3分） （2） 邻接矩阵；（2分） （3） 邻接表；（2分） （4） 画出其强连通分量。（3分）
得分 评卷人 顶点 1 2 3 4 5 6 入度 出度 5
3.已知某字符串s中共有8种字符(a,b,c,d,e,f,g,h)，各种字符分别出现2次，1次，4次，5次，7次，3次，4次和9次，对该字符串用{0，1}进行前缀编码，问该字符串的编码至少有多少位(提示:画出哈夫曼树并求出WPL值)？ （12分）
学 院 课头号 班 级
姓名 学号
………………………………………………密………………………线………………………
…
…………………… 6
4.已知有向图，从顶点v1出发按普里姆算法求其最小生成树，按生成次序写出各条边。 （8分）
5.对任意输入的一个非负十进制整数，打印输出其二进制数，要求写出算法以及栈的结构定义（顺序，链式都可以）。 （10分） 7
08-09-1学期《数据结构》A答案及评分标准 一、判断 （共10分） 1.×2.×3.×4.×5.×6.×7.√8.√9.√10.× (每题1分) 二、选择（共20分） 1.B 2.C 3.B 4.C 5.C 6.A 7.C 8.B 9.C 10.B （每题2分） 三、填空（每空1分，共20分） 1.逻辑结构、存储结构、运算 2.500、499 3.长度相等、对应字符相等 4.n-1 5.有穷性，可行性，输出 6.尾部，首部，栈顶 7.O（n） 8.是不 9.120log2 10. ( rear - front + m) % m 11.顺序查找、折半查找（任意查找算法） 四、应用（50分） 1、
Null
图5分 先序序列ABCDEGFIH (2分) 线索化3分 2、
A B G
C D F H
E I 8
3、画出树5分，写成字符编码4分，求出wpl值3分。 A B C D E F G H 00000 00001 100 001 11 0001 101 01
wpl=5×2+5×1+4×3+3×5+2×9+3×4+3×4+2×7＝98 该字符串编码长度至少为98位。
35 2 1 3 4 4 7 8 15 6 5 20 11 9 3 9
4. 图画出5分，生成次序为V1 V2 V7 V3V4 V5 V6 (3分) 5.typedef struct {selemtype *base; Selemtype *top; }sqstack; 写出结构定义给4分 Void conversion() { initstack(S); Scanf(“%d”，N); While (N) {push(S,N % 2); N=N/2; } While(! StackEmty(S)) {pop( S,e ); Printf(“%d”,e); } } 算法给6分
1 2 3 7 4 5 6
