山东：07年专升本考试数据结构模拟试题1
专升本《数据结构》试卷
一、填空题：（每小题2分，共10分）
1. 设有数据结构（D，R），其中 D 是数据元素的有限集，R 是的有限集。
2. 深度为 k 的二叉树其结点数至多有个。
3. 栈是一种特殊的线性表，它允许在表的一端进行操作。
4. 通常象交通、道路问题的数学模型是一种称为的数据结构。
5. 哈希表是一种查找表，可以根据哈希函数直接获得。
二、单项选择题：（每小题2分，共10分）
对于下列各题，在备选答案中选出一个正确的，并将其编号填在“ ”位置上。
1. 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用存储方式最节省运算时间。
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
2. 下列排序算法中，算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。。
A. 直选择排序
B. 冒泡排序
C. 归并排序
D. 堆排序
3. 队列的操作原则是。
A. 先进后出
B. 先进先出
C. 只能进行插入
D. 只能进行删除
4. 在具有 n 个结点的二叉链表中，非空的链域个数为。
A. n-1
B. n
C. n 1
D. 不确定
5. 对具有 n 个元素的有序查找表采用折半查找算法查找一个键值，其最坏比较次数的数量级为。
A. O(log2n)
B. O(n)
C. O(nlog2n)
D. O(n2)
三、判断题：（每小题2分，共10分）
判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。
1. 在栈为空的情况下不能作出栈处理，否则，将产生下溢出。（）
2. 如果有向图 G=(V, E) 的拓扑序列唯一，则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。（）
3. 在大根堆中，必定满足每个结点的键值大于其左右子树中所有结点的键值。（）
4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（）
5. 在索引顺序表中，对索引表既可采用顺序查找，也可采用二分查找。（）
四、解答下列各题：（每题10分，共40分）
1. 已知线性表 L 采用带头结点的的单向循环链表表示，试给出它的存储结构类型描述及相应的示意图。。
2. 已知一棵二叉树的先序、中序和后序序列如下所示，请填写各序列中空格处的结点，并画出该二叉树的二叉链表存储结构示意图。
先序序列是：_ B _ F _ I C E H _ G；中序序列是：D _ K F I A _ E J C _ ；
后序序列是：_ K _ F B H J _ G _ A
3. 已知数据表为（48，70，33，65，24，56，12，92，86，22），a) 写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果；b) 写出按基数排序思想对最低位进行一次分配和收集的结果。
4. 对图1所示的带权无向图，写出它的邻接矩阵和深度优先搜索序列，并按克鲁斯卡算法求其最小生成树（写出求解的详细过程示意图）。
图1 带权无向图
五、算法设计题：（前两题必做，每题15分，共30分；第三题为附加题，选做，10分）
1. 已知队列 Q 以循环队列存储。写出 Q 的存储结构类型描述，并试编写算法实现将元素 x 插入队列 Q 的入队操作 EnQueue(Q,x)和从队列 Q 中获取队首元素的函数 GetTop(Q)。
2. 假设线性表L=(a1,a2,……,an) 用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,……,
a2,a1)。
3. 设非空二叉树 T 采用中序线索二叉链表表示，写出 T 的存储结构类型描述。试编写算法 InOrderTraverse(T) 实现对二叉树 T 的中序遍历。
(A )数据的逻辑结构 (B )数据的存储结构 《数据结构》专升本考试试题 (2015 年 3 月) (C )数据的逻辑结构和存储结构 12.算法分析的两个主要方面是( (A )空间复杂度和时间复杂度 (C )可读性和文档性 (D )数据的逻辑结构、存储结构及其基本操作 )o (B )正确性和简单性 (D )数据复杂性和程序复杂性 一、单项选择题(本大题共 20小题，每小题2分，共40分) 1 ?对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为( (A) 正确性 (B) 可行性 ( C) 健壮性 2 ?设S 为C 语言的语句,计算机执行下面算法时， for(i=n-1 ； i>=0 ； i--) for(j=0 ; jn ext==head (B ) p-> next==NULL (C ) p==NULL (D ) p==head 16. 一个栈的输入序列为： a ，b ，c ，d ，e ，则栈的不可能输出的序列是( )o (A ) a,b,c,d,e (B ) d,e,c,b,a (C ) d,c,e,a,b (D ) e,d,c,b,a 17.设SUBSTR(S,i,k)是求S 中从第i 个字符开始的连续k 个字符组成的子串的操作，则对 5 ?深度为k 的完全二叉树，其叶子结点必在第( (A ) k-1 (B ) k (C ) k-1 和 k (D ) 6?具有60个结点的二叉树，其叶子结点有12个， (A ) 11 ( B ) 13 (C ) 48 ( D 37 利于删除操作 利于随机访问 )层上。 1至k 则度为1的结点数为( 7.图的Depth-First Search(DFS) 遍历思想实际上是二叉树( (A )先序 (B )中序 (C )后序 (D )层序 8 .在下列链队列Q 中，元素a 出队的操作序列为( )遍历方法的推广。 S= ' Beijing&Nanjing '，SUBSTR(S,4,5)=( ) (A )‘iji ng ' (B )' jing& ' (C )' ingNa ' (D ) 'ing&N ' 18.广义表((a),a) 的表尾是( )o (A ) a (B ) (a) (C )() (D ) ((a)) 19. 在一棵具有5层的满二叉树中结点总数为( )o (A ) 31 (B ) 32 (C ) 33 (D ) 16 20. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )o (A )完全图 (B )连通图 (C )有回路 (D ) —棵树 二、填空题(本大题共20个空，每空2分，共40分) Q (A ) (B ) (C ) (D ) p=Q.fr ont->n ext; p->n ext= Q.front->n ext; p=Q.fr ont->n ext; Q.front->n ext=p->n ext; p=Q.rear- >n ext; p->n ext= Q.rear- >n ext; p=Q->n ext; Q->n ext=p->n ext; 1 .逻辑结构决定了算法的 ____________ ，而存储结构决定了算法的 _____________ o 2. _______________________ 栈和队列都是一种 ______________________ 的线性表，栈 和删除只能在 ______________ 进行。 3. 线性表(a 1,a 2,…,a n )的顺序存储结构中，设每个单元的长度为L,元素a i 的存储地址LOC 4. 已知一双向链表如下(指针域名为next 和prior): 9. Huffman 树的带权路径长度WP 等于( (A )除根结点之外的所有结点权值之和 (C )各叶子结点的带权路径长度之和 )域存储后继结点的地址。 (C ) rchild (D ) root )o 10?线索二叉链表是利用( (A ) Ichild (B ) data 11 ?研究数据结构就是研究( (B ) (D ) ) 所有结点权值之和 根结点的值 现将p 所指的结点插入到x 和y 结点之间，其操作步骤为： ________________________ 5 . n 个结点无向完全图的的边数为 ________________________ ， n 个结点的生成树的边 为 ____________________ o
《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 山东:07年专升本考试数据结构模拟试题1 一、填空题:(每小题2分,共10分 1. 设有数据结构(D,R,其中 D 是数据元素的有限集,R 是的有限集。 2. 深度为 k 的二叉树其结点数至多有个。 3. 栈是一种特殊的线性表,它允许在表的一端进行操作。 4. 通常象交通、道路问题的数学模型是一种称为的数据结构。 5. 哈希表是一种查找表,可以根据哈希函数直接获得。 二、单项选择题:(每小题2分,共10分 对于下列各题,在备选答案中选出一个正确的,并将其编号填在“”位置上。 1. 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值,则采用存储方式最节省运算时间。 A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表 2. 下列排序算法中,算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。。 A. 直选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序 3. 队列的操作原则是。 A. 先进后出 B. 先进先出 C. 只能进行插入 D. 只能进行删除 4. 在具有 n 个结点的二叉链表中,非空的链域个数为。 A. n-1 B. n C. n+1 D. 不确定 5. 对具有 n 个元素的有序查找表采用折半查找算法查找一个键值,其最坏比较次数的数量级为。 A. O(log2n B. O(n C. O(nlog2n D. O(n2 三、判断题:(每小题2分,共10分 判断下列各题是否正确,若正确,在题后的括号内填“T”,否则填“F”。 1. 在栈为空的情况下不能作出栈处理,否则,将产生下溢出。( 2. 如果有向图 G=(V, E 的拓扑序列唯一,则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。( 3. 在大根堆中,必定满足每个结点的键值大于其左右子树中所有结点的键值。( 4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。( 5. 在索引顺序表中,对索引表既可采用顺序查找,也可采用二分查找。( 四、解答下列各题:(每题10分,共40分 1. 已知线性表 L 采用带头结点的的单向循环链表表示,试给出它的存储结构类型描述及相应的示意图。。 2. 已知一棵二叉树的先序、中序和后序序列如下所示,请填写各序列中空格处的结点,并画出该二叉树的二叉链表存储结构示意图。 先序序列是:_ B _ F _ I C E H _ G;中序序列是:D _ K F I A _ E J C _ ; 后序序列是:_ K _ F B H J _ G _ A 3. 已知数据表为(48,70,33,65,24,56,12,92,86,22,a 写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果;b 写出按基数排序思想对最低位进行一次分配和收集的结果。 4. 对图1所示的带权无向图,写出它的邻接矩阵和深度优先搜索序列,并按克鲁斯卡算法求其最小生成树(写出求解的详细过程示意图。 图1 带权无向图 五、算法设计题:(前两题必做,每题15分,共30分;第三题为附加题,选做,10分 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。 一．选择题（每小题1分，共8分） 1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址为100，每个元素占1个地址空间，则a[3][2]的地址为（）。 （A）102 （B）105 （C）106 （D）108 2.森林转换为二叉树后，从根结点开始一直沿着右子数下去，一共有4个结点，表明（）。 （A）森林有4棵树（B）森林的最大深度为4 （C）森林的第一棵树有4层（D）森林有4个结点 3.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。 （A）e （B）2e （C）n^2－e （D）n^2－2e 4.在内部排序中，排序时不稳定的有（）。 （A）插入排序（B）冒泡排序（C）快速排序（D）归并排序 5.设一数列的顺序为1，2，3，4，5，通过栈结构不可能派成的顺序数列为（）。 （A）3，2，5，4，1 （B）1，5，4，2，3 （C）2，4，3，5，1 （D）4，5，3，2，1 6.一个n条边的连通无向图，其顶点的个数至多为（）。 （A）n－１（B）n（C）n＋１（Ｄ）nlog2n 7.总共3层的完全二叉树，其结点数至少有（）个。 （A）3 （B）4 （C）7 （D）8 8.已知某算法的执行时间为（n^3+n^2+n）log2（n+2），n为问题规模，则该算法的时间复杂度是（）。 （A）O（n）（B）O（n^2） （C）O（log2n）（D）O（n^3log2n） 二．判断题（每题1分，共8分。正确的打√，错误的打×） 1.只要是算法，肯定可以在有限的时间内完成。（） 2.无论是线性表还是树，每一个结点的直接前驱结点最多只有一个。（） 3.不论是行优先还是列优先，二维数组的最后一个元素的存储位置是一样的。（） 4.直接插入排序时，关键码的比较次数与记录的初始排列无关。（） 5.二叉树的先序遍历不可能与中序遍历相同。（） 6.任何一棵二叉树，不可能没有叶子结点。（） 7.一个稀疏矩阵采用三元组法存储不可能是（5，3，7），（5，4，4），（5，3，5）。（） 8.一个无序的顺序表不能采用折半查找法进行查找。（）。 《数据结构》专升本考试试题 (2015年3月) 一、单项选择题(本大题共20小题,每小题2分,共40分) 1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为( )。 (A) 正确性 (B) 可行性 (C) 健壮性 (D) 输入性 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为( )。 for(i=n-1;i>=0;i--) for(j=0;j 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 学习-----好资料 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后 专升本《数据结构》 一、（共75题,共150分） 1. 数据的基本单位是（）。（2分） A.数据元素 B.记录 C.数据对象 D.数据项 .标准答案：A 2. （）是数据的不可分割的最小单位。（2分） A.数据对象 B.数据元素 C.数据类型 D.数据项 .标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分） A.时间效率 B.空间效率 C.可读性 D.健壮性 .标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分） A.栈 B.队列 C.串 D.数组 .标准答案：B 5. 串的长度是指串中所含（）的个数。（2分） A.不同字符 B.不同字母 C.相同字符 D.所有字符 .标准答案：D 6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分） A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 .标准答案：B 8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分） A.64 B.32 C.16 D.8 .标准答案：A 9. 深度为h的二叉树，第h层最多有（）个结点。（2分） A.h B.2h-1 C.2h-1 D.2h .标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分） A.m B.m+1 C.2m D.m-1 .标准答案：B 11. 下面叙述错误的是（）。（2分） A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象 C.有向图的邻接矩阵一定是对称的 D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的 .标准答案：C 12. 以下与数据的存储结构无关的术语是（）。（2分） A.循环队列 B.双向链表 C.哈希表 D.数组 .标准答案：D 13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分） A.O(1) B.O(log n) C.O(n) D.O(n2) .标准答案：A 14. 在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分） A.k B.k-1 C.2k D.k+1 .标准答案：D 15. 在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：C 16. 16某二叉树的后序遍历序列和和中序遍历序列均为abcd，该二叉树的前序遍历序列是（）。（2分） A.abcd B.dcba C.acbd D.dbca .标准答案：B 17. n个顶点的无向连通图的生成树，至少有（）个边。（2分） A.n(n-1) B.n(n-1)/2 C.2n D.n-1 .标准答案：D 18. 可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分） A.队列 B.树 C.栈 D.集合 .标准答案：A 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 第一章英语；英语整体上看试卷一共分为六道大题，一是单项选择题；试题分析；一单项选择：20’；ishelpfulinlookingforajo；A.certificateB.grad eC.re；A.senseB.savingC.imforma；A.momentB.pointC.heartD.；4.Mymebysa yingthatIcould；A.discou 第一章英语 英语整体上看试卷一共分为六道大题，一是单项选择题共计20道20分；二是完型填空10道10分；三是阅读，分三个篇章，每个篇章5道选择，各2分，总计30分；四是用词的适当形式填空，10道10分；五是翻译(汉译英)，5道2 0分；六是写作10分；总计100分。 试题分析 一单项选择：20’ is helpful in looking for a job，but it doesn’t mean a job. A.certificate B.grade C.record D.debt A.sense B.saving C.imformation https://www.doczj.com/doc/085499108.html,fort A.moment B.point C.heart D.face 4.My me by saying that I could win in the speech contest ,so I to ok part in it. A.discouraged B.encouraged C.courage D.asked 5.His new book to the top as the bestseller. A.rocketed B.raised C.stayed D.reached 6.The president was invited to address the audience at the openin g Of the Olympic Games. A.ceremony B.speech C.meeting D.celebration 7.In some western is that blank cats will bring misforture to peo ple. A.superstar B.superpower C.superstitious D.superstition 8.The the cup from the table with any guest’s knowledge . A.reminded B.reduced C.refused D.removed A.looks B.sets C.symbolizes D.Seeks 10.Although we are of the same age,we height and weight. 11.Some soldiers are very his orders strictly. A.loyalty B.loyal C.faithfulness D.faith （损坏）. A.What B.whatever C.who D.whoever 13.All of those the peace conference were asked to sign their nam es on piece of cloth. A.attended B.preseted C.went D. was 课程测试试题（卷） ----------------------以下为教师填写-------------------- I、命题院（部）：数学与计算机科学学院 II、课程名称：数据结构 III、测试学期：20 －20 学年度第学期 IV、测试对象：学院专业级班 V、问卷页数（A4）：页 VI、答卷页数（A4）：页 VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号） 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指 向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多 可以组成( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 ( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述 序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四 种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 _________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是 ________________;删除一个结点时，需要执行的操作是 ______________________________（假设栈不空而且无需回收被删除结点）。 专升本《数据结构》模拟题试卷 一. （共75题,共150分） 1. 数据的基本单位是（）。（2分） A.数据元素 B.记录 C.数据对象 D.数据项 ★检查答案标准答案：A 2. （）是数据的不可分割的最小单位。（2分） A.数据对象 B.数据元素 C.数据类型 D.数据项 ★检查答案标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分） A.时间效率 B.空间效率 C.可读性 D.健壮性 ★检查答案标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分） A.栈 B.队列 C.串 D.数组 ★检查答案标准答案：B 5. 串的长度是指串中所含（）的个数。（2分） A.不同字符 B.不同字母 C.相同字符 D.所有字符 ★检查答案标准答案：D 6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2 分） A.1 B.2 C.3 D.4 ★检查答案标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分） A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 ★检查答案标准答案：B 8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分） A.64 B.32 C.16 D.8 ★检查答案标准答案：A 9. 深度为h的二叉树，第h层最多有（）个结点。（2分） A.h B.2h-1 C.2h-1 D.2h ★检查答案标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分） A.m B.m+1 C.2m D.m-1 ★检查答案标准答案：B 11. 下面叙述错误的是（）。（2分） A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象数据结构模拟试题及答案
山东07年专升本考试数据结构模拟试题.
数据结构模拟试题1
《数据结构C》模拟试题
数据结构模拟试题9
专升本试题数据结构
《数据结构》模拟试卷一及答案
数据结构模拟试题一及答案汇编
专升本《数据结构》_试卷_答案
数据结构模拟试卷(含答案)
专升本考试试题分析包括英语高数数据结构考试原题
数据结构期末模拟试题05(有答案)
专升本《数据结构》模拟题试卷
相关主题
文本预览