数据结构真题2013年10月
数据结构真题2013年10月
(总分：100.01，做题时间：90分钟)
一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00)
1.算法的时间复杂度表征的是______
∙ A.算法的可读性
∙ B.算法的难易程度
∙ C.执行算法所耗费的时间
∙ D.执行算法所耗费的存储空间
（分数：2.00）
A.
B.
C. √
D.
解析：[考点] 算法的时间复杂度定义 [解析] (1)执行算法所耗费的时间，即时间复杂性；(2)执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；(3)算法应易于理解、易于编程、易于调试等，即可读性和可操作性。因此表征算法时间复杂度的是执行算法耗费的时间，C正确。
2.对需要频繁插入和删除结点的线性表，适合的存储方式是______
∙ A.顺序存储
∙ B.链式存储
∙ C.索引存储
∙ D.散列存储
（分数：2.00）
A.
B. √
C.
D.
解析：[考点] 链式存储方式 [解析] 应该采用链式存储结构。因为采用链式结构存储线性表，插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。但移动指针域操作比移动元素操作花费的时间少得多。
3.在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是______
∙ A.p-＞next-＞next==head
∙ B.p-＞next==head
∙ C.p-＞next-＞next==NULL
∙ D.p-＞next==NULL
（分数：2.00）
A.
B. √
C.
D.
解析：[考点] 循环链表的特点 [解析] 循环链表的特点是单链表中最后一个结点(终端结点)的指针域不为空，而是指向链表的头结点，使整个链表构成一个环；循环结束的判断条件不再是P或P→next是否为空，而是他们是否等于头指针。因此答案选B。
4.迪杰斯特拉(Dijkstra)算法的功能是______
∙ A.求图中某顶点到其他顶点的最短路径
∙ B.求图中所有顶点之间的最短路径
∙ C.求图的最小生成树
∙ D.求图的拓扑排序序列
（分数：2.00）
A. √
B.
C.
D.
解析：[考点] 迪杰斯特拉(Dijkstra)算法的功能[解析] Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算从某个源点到其余各定点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。因此答案为A。
5.若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能获得的出栈序列是______
∙ A.4，5，3，2，1
∙ B.4，3，5，1，2
∙ C.1，2，3，4，5
∙ D.5，4，3，2，1
（分数：2.00）
A. √
B.
C.
D.
解析：[考点] 栈的特点
[解析] 栈是限定仅在表尾进行插入或删除操作的线性表，因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。假设一个栈S中的元素为a n，a n-1，…，a1，则称a1为栈底元素，a n为栈顶元素。栈中的元素按a1，a2，…，a n-1，a n的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(LastInFirstOut)表，简称为LIFO表。
A：1进2进3进4进4出5进5出3出2出1出出栈序列为45321
B：1进2进3进4进4出3出5进5出2出1出出栈序列为43521
C：1进1出2进2出3进3出4进4出5进5出出栈序列为12345
D：1进2进3进4进5进5出4出3出3出1出出栈序列为54321
所以答案选B。
6.A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1000，若每个元素占两个字节，则元素A[3][3]的存储地址为______
∙ A.1015
∙ B.1016
∙ C.1028
∙ D.1030
（分数：2.00）
A.
B.
C.
D. √
解析：[考点] 数组的顺序存储 [解析] 数组的顺序存储分为行优先存储和列优先存储，数组A[m，n]为m 行n列的数组，d为每个元素占的字节数，按行优先顺序存储的二维数组，A[0，0]是基地址：地址计算公式LOC(ai，j)=LOC(a00)+[i×n+j]×d三维数组A[m，n，p]按行优先顺序位于内存中，计算数组元素a[i，j，k]的地址为LOC(aij)=LOC(a000)+[i×n×p+j×p+k]×d 根据公式带入可知D选项正确。
7.深度为4的完全二叉树的结点数至少为______
∙ A.4
∙ B.8
∙ C.13
∙ D.15
（分数：2.00）
A.
B. √
C.
D.
解析：[考点] 完全二叉树 [解析] 完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称为完全二叉树。若设二叉树的深度为h，除第h层外，其他各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。要想使深度为4的完全二叉树节点数最少，那么第一、二、三层的结点数都达到最大，分别为21-1，22-1，23-1，第四层的结点最多为24-1，最少为1，那么整个完全二叉树最少结点数为8，因此答案选B。
8.若采用邻接矩阵A存储有向图G，则结点k的入度等于A中______
∙ A.结点k对应行元素之和
∙ B.结点k对应列元素之和
∙ C.结点k对应行和列元素之和
∙ D.非零元素之和
（分数：2.00）
A.
B. √
C.
D.
解析：[考点] 有向图图的邻接矩阵表示法 [解析] 邻接矩阵是表示图形中顶点之间相邻关系的矩阵，第k 列表示终点为顶点k的那些边，非0表示这条边存在，入度表示终点为这点的边数之和，即对应列非零元素之和即为结点k的入度，因此答案选B。
9.无向图G的邻接矩阵一定是______
∙ A.对称矩阵
∙ B.对角矩阵
∙ C.三角矩阵
∙ D.单位矩阵
（分数：2.00）
A. √
B.
C.
D.
解析：[考点] 无向图的邻接矩阵表示法的特点 [解析] 无向图的邻接矩阵是按主对角线对称的，因此无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称，答案选A。
10.下列关于有向带权图G的叙述中，错误的是______
∙ A.图G的任何一棵生成树都不含有回路
∙ B.图G生成树所含的边数等于顶点数减1
∙ C.图G含有回路时无法得到拓扑序列
∙ D.图G的最小生成树总是唯一的
（分数：2.00）
A.
B.
C.
D. √
解析：[考点] 图的生成树 [解析] 采用不同的遍历方法可以得到不同的生成树，从不同的顶点出发进行遍历也可以得到不同的生成树，所以图的生成树不是唯一的，因此答案D表述错误。树定义为一个无回路的连通图，因此任何一棵生成树都不含有回路，A正确。一棵具有n个顶点的生成树有仅有n-1条边，因此生成树所含的边数等于顶点数减1，B正确。在AOV网中，若不存在回路(环)，所有的活动才排成一个线性序列，C正确。
11.在下列排序算法中，关键字比较次数与初始排列次序无关的是______
∙ A.冒泡排序
∙ B.希尔排序
∙ C.直接插入排序
∙ D.直接选择排序
（分数：2.00）
A.
B.
C.
D. √
解析：[考点] 内部排序方法的分析比较 [解析] 关键字比较次数与记录的初始顺序无关的排序方法是选择排序。(1)若待排序的一组记录数目n较小(如n≤50)时，可采用插入排序或选择排序。(2)若n较大时，则应用采用快速排序、堆排序或归并排序。 (3)基待排序记录按关键字基本有序时，则适宜选用直接插入排序或冒泡排序。 (4)当n很大，而且关键字位数较少时，采用链式基数排序较好。 (5)关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。
12.对下图进行拓扑排序，可以得到的拓扑序列是______
∙ A.a b c d e
∙ B.b a c d e
∙ C.b c a d e
∙ D.a b d c e
（分数：2.00）
A.
B. √
C.
D.
解析：[考点] 拓扑排序 [解析] 拓扑排序方法如下： (1)在从有向图中选择一个没有前驱(即入度为0)的顶点并且输出。 (2)从网中删去该顶点，并且删去从该顶点发出的全部有向边。 (3)重复上述两步，直至全部顶点均已输出，或者当前图中剩余的顶点中没有前趋(入度为0)顶点为止。 (4)输出剩余的无前趋结点。由于结点a的入度不为0，因此首先排除A，D；b的入度为0，输出b，删除顶点b和从该点出发的全部有向边，接着找入度为0的结点，此时顶点a的入度为0，而顶点c的入度不为0，因此答案选B。
13.下列线性表中，能使用二分查找的是
∙ A.顺序存储(2，12，5，6，9，3，89，34，25)
∙ B.链式存储(2，12，5，6，9，3，89，34，25)
∙ C.顺序存储(2，3，5，6，9，12，25，34，89)
∙ D.链式存储(2，3，5，6，9，12，25，34，89)
（分数：2.00）
A.
B.
C. √
D.
解析：[考点] 二分法查找的使用条件 [解析] 二分法查找要求查找对象的线性表必须是顺序存储结构的有序表，因此排除B和D，又因为A选项中不是有序表，因此答案选C。
14.在下列查找方法中，平均查找长度与结点数量无直接关系的是______
∙ A.顺序查找
∙ B.分块查找
∙ C.散列查找
∙ D.基于B树的查找
（分数：2.00）
A.
B.
C. √
D.
解析：[考点] 散列表的查找
[解析] 顺序查找成功的平均查找长度为(n+1)/2，折半查找的平均查找长度为log2(n+1)-1，分块查找的平均查找长度为(((n/s)+s)/2)+1，其中s为表分块后每一块的记录个数，可见分块查找不仅与表长n有关，还与每一块中的记录个数s有关，二叉树查找类似于折半查找，哈希表的平均查找长度不是节点个数n的函数，而是装填因子的函数，与节点个数无关，只依赖于哈希表的装填因子，因此选C。
15.下列排序算法中，时间复杂度为O(nlog2n)的算法是______
∙ A.快速排序
∙ B.冒泡排序
∙ C.直接选择排序
∙ D.直接插入排序
（分数：2.00）
A. √
B.
C.
D.
解析：[考点] 内部排序方法的时间复杂度
[解析] 排序算法的时间复杂度和空间复杂度如下所列：
[*]
时间复杂度为O(nlog2n)的排序算法有快速、归并、堆排序，因此答案选A。
二、{{B}}填空题{{/B}}(总题数：10，分数：20.00)
16.数据的同一种逻辑结构，可以对应多种不同的______。
（分数：2.00）
填空项1:__________________ （正确答案：物理结构或存储结构）
解析：[考点] 逻辑结构和物理结构的概念 [解析] 数据逻辑结构描述的是数据元素之间的逻辑关系，数据结构在计算机中的表示(又称映像)称为数据的物理结构，又称存储结构。数据结构的存储结构是和相应的数据在内存中的物理地址之间的关系有关，而逻辑结构只是描述数据之间的关系，同一种逻辑结构可以用多种物理结构存储，可以采用顺序存储或者链式存储等多种方式。可见，数据的同一种逻辑结构，可以对应多种不同的存储结构。
17.若在长度为n的顺序表第i个元素之前插入一个元素，则需要向后移动的元素个数是______。
（分数：2.00）
填空项1:__________________ （正确答案：n-i+1）
解析：[考点] 顺序表上的基本运算 [解析] 一般情况下，在第i(1≤i≤n)个元素之前插入一个元素时，需将第n至第i个元素向后移动一个位置，第n至第i个元素一共是n-i+1个元素。
18.顺序栈存放在S[m]中，S[0]为栈底，栈顶指针top初始值为-1，则栈满的条件是top=______。
（分数：2.00）
填空项1:__________________ （正确答案：m-1）
解析：[考点] 栈的顺序存储结构 [解析] 设顺序栈存放在S.data[maxsize]中，栈底位置是maxsize-1，栈空的条件S.top==maxsize，栈满的条件S.top==0；设顺序栈存放在S.data[maxsize]中，栈底位置是-1，栈空条件是S.top==-1，栈满条件是S.top==maxsize-1，由此可得答案为m-1。
19.队列只能在队尾进行插入操作，在队首进行______操作。
（分数：2.00）
填空项1:__________________ （正确答案：删除）
解析：[考点] 队列的定义 [解析] 队列是一种先进先出(FIFO)的线性表，它只允许在表的一端进行插入，在另一端进行删除；在队列中，允许插入的一端叫做队尾，允许删除的一端称为对首。
20.广义表A=(x，((y，z)，a，b))，则函数head(laead(tail(A)))的值是______。
（分数：2.00）
填空项1:__________________ （正确答案：(y，z)）
解析：[考点] 广义表的基本运算
[解析] 广义表一般记作：LS=(a1，a2，…，a n)其中LS是广义表的名称，n是它的长度，a i可以是单个元素也可是广义表，分别称为原子和子表，当广义表非空时，称第一个元素a1为LS的表头，称其余元素组成的广义表(a2，a3，…，a n)为表尾。
21.以权值分别为4，3，2，1的四个叶子结点构成的哈夫曼树，其带权路径长度WPL是______。
（分数：2.00）
填空项1:__________________ （正确答案：19）
解析：[考点] 哈夫曼树的带权路径长度 [解析] 首先1与2结合生出3节点，再选剩下的3与刚生成的3结合生出6节点，剩下的4小于6，所以4，6结合生出10根节点。对新生成的哈夫曼树进行编码，1的路径000，2的路径001，3的路径01，4的路径为1，因此WPL=1*3+2*3+3*2+4*1=19。
22.图的遍历方法有两种，一种是深度优先遍历，另一种是______。
（分数：2.00）
填空项1:__________________ （正确答案：广度优先遍历）
解析：[考点] 图的遍历方法 [解析] 图的遍历方法一共有两种，分别是深度优先遍历和广度优先遍历。23.如果排序算法是稳定的，则关键字相同的两个记录排序前后相对次序______。
（分数：2.00）
填空项1:__________________ （正确答案：不变）
解析：[考点] 排序算法基本概念 [解析] 假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定；否则称其不稳定。因此如果排序算法是稳定的，那么关键字相同的两个记录排序前后的相对次序是不变的。
24.已知散列表表长m=11，散列函数h(key)=key%11，表中存有三个关键字15，27，39，其余地址为空，若采用线性探查法处理冲突，则关键字为60的结点保存的地址是______。
（分数：2.00）
填空项1:__________________ （正确答案：7）
解析：[考点] 处理冲突的方法
[解析] H i=(H(key)+d i)MODm，i=1，2，…，k(k＜=m-1)，其中H(key)为散列函数，m为散列表长，d i为增量序列，可有下列三种取法：①d i=1，2，3，…，m-1，称线性探测再散列；②d i=12，-12，22，-22，32，…，±k2，(k≤m/2)称二次探测再散列；③d=伪随机数序列，称伪随机探测再散列；根据散列函数h(key)=key%11，求得关键字15，27，39的散列值分别为4、5、6，现有关键字60，散列值为5，产生冲突，根据线性探测再散列得到地址6，仍然冲突，再求下一个地址7，7的位置为“空”地址，因此应该填入的地址为7。
25.已知图G的邻接表如下图所示。v1出发进行深度优先搜索，得到的深度优先搜索序列是______。
（分数：2.00）
填空项1:__________________ （正确答案：v1、v4、v3、v5、v2）
解析：[考点] 图的遍历 [解析] 深度优先搜索(DFS)类似于树的先根遍历。深度优先遍历图的方法是从图中某顶点v出发：(1)访问顶点v；(2)依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；(3)若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历。
三、{{B}}解答题{{/B}}(总题数：2，分数：20.00)
设Q[M]是有M个元素存储空间的循环队列，若front指向队首元素，rear指向队尾元素的下一位置，请分别用C语言描述下列操作。（分数：5.01）
(1).将元素x入队。（分数：1.67）
__________________________________________________________________________________________ 正确答案：(Q→rear=(Q→rear+1)%m)
解析：
(2).将队首元素出队，并保存到变量y中。（分数：1.67）
__________________________________________________________________________________________ 正确答案：(y=Q→data[Q→front] Q→front=(Q→front+1)%m)
解析：
(3).计算当前队列中元素的个数。（分数：1.67）
__________________________________________________________________________________________ 正确答案：((Q→rear-Q→front+m)%m)
解析：[考点] 循环队列
已知带权图G=(VE)，其中V=(A，B，C，D，E)，邻接矩阵如下所列。
（分数：15.00）
(1).画出对应的图G。（分数：3.75）
__________________________________________________________________________________________ 正确答案：(对应的带权图G [*])
解析：
(2).画出图G的最小生成树。（分数：3.75）
__________________________________________________________________________________________ 正确答案：(克鲁斯卡尔算法生成的最小生成树： [*])
解析：[考点] 最小生成树
(3).已知一组待排记录的关键字序列为(15，11，17，59，14，35，13，17，24，84)，请给出对应的小根堆序列。（分数：3.75）
__________________________________________________________________________________________ 正确答案：(11，14，13，17，15，35，17，59，24，84)
解析：[考点] 堆排序
(4).已知二叉树如下图所示，请画出该二叉树的前序线索。 3.75）
__________________________________________________________________________________________ 正确答案：(见下图 [*])
解析：[考点] 二叉树的线索化
四、{{B}}算法阅读题{{/B}}(总题数：3，分数：20.00)
阅读下列函数并回答问题。
typedef struct node{
DataType data;
struct node*next;
}LinkNode;
Typedef LinkNode*Linklist;
void DeleX(Linklist head, DataType x)
{
LinkNode*p, *q, *s;
p=head; q=p--＞next;
while(q!=NULL)
if(q-＞data==x){
s=q; q=q-＞next;
free(s); p-＞next=q;
}
else{
p=q; q=q-＞next;
}
}（分数：5.00）
(1).执行该函数后，单链表head中data值为x的结点数是多少?（分数：2.50）
__________________________________________________________________________________________ 正确答案：(0个)
解析：
(2).该函数的功能是什么?（分数：2.50）
__________________________________________________________________________________________ 正确答案：(该函数的功能是删除单链表中值为x的节点。)
解析：[考点] 单链表删除操作 [解析] 在DeleX()函数中通过while循环，依次遍历单链表head，q指向当前比较的节点，p指向当前节点的前一个节点，在判断的过程中，如果当前节点q指向的节点data值等于x则首先将q后移，然后删除该节点(p＞next=q)；如果不相等，则将p，q分别后移一个节点。
阅读下列函数并回答问题。
typedef struct node{
DataType data;
struct node*lchild, *rchild;
}BinTNode;
typedef B inTNode*BinTree;
void Inorder(BinTree bt)
{
if(bt!=NULL){
Inorder(bt-＞lchild);
printf("%c", bt-＞data);
Inorder(bt-＞rchild);
}
}（分数：9.99）
(1).写出对如下图所示的二叉树执行函数Inorder后得到的输出序列。 3.33）
__________________________________________________________________________________________ 正确答案：(CDBFEA)
解析：
(2).该函数的功能是什么?（分数：3.33）
__________________________________________________________________________________________ 正确答案：(函数的功能是对二叉树进行后序遍历。)
解析：[考点] 遍历二叉树 [解析] 函数对给定的节点，首先判断该节点是否为空，如果不为空则首先对左子树进行递归判断，然后再对右子树进行递归判断，每次递归结束则输出当前节点。
(3).下列函数实现直接插入排序，请填写适当内容，使其功能完整。 void f32(int r[], int N) { int i, j; for(i=2; ______; ______) { r[0]-r[i]; j=i-1; while(______) { r[j+1]=r[j]; j=j-1; }
r[j+1]=r[0]; } }（分数：3.33）
__________________________________________________________________________________________ 正确答案：(i＜N i++; r[j]＞r[0])
解析：[考点] 直接插入排序 [解析] 直接插入排序(InsertionSort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。同时为了防止在插入的过程中出现数组下标出界，在r[0]处设置监视哨。设数组为a[0…n-1]。 (1)初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1。(2)将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。 (3)i++并重复第二步直到i==n-1，排序完成。
函数BinSearch实现二分查找，请回答下列问题。
int BinSearch(SeqList R, KeyType k, int n)
{ int low=0, mid, high=n-1;
while(low＜=high){
mid=______;
if(R[mid]. key==k)
return mid;
if(R[mid]. key＞k)
high=mid-1;
else
low=mid+1;
}
return-1;
}（分数：5.01）
(1).在空白处填写适当内容，使函数功能完整。（分数：1.67）
__________________________________________________________________________________________ 正确答案：((low+high)/2)
解析：
(2).查找成功时函数的返回值是什么?（分数：1.67）
__________________________________________________________________________________________ 正确答案：(成功时返回待查元素所在的位置)
解析：
(3).查找失败时函数的返回值是什么?（分数：1.67）
__________________________________________________________________________________________ 正确答案：(失败返回-1)
解析：[考点] 二分查找 [解析] 二分查找查找所要查找的元素时，首先与序列中间的元素进行比较，如果大于这个元素，就在当前序列的后半部分继续查找；如果小于这个元素，就在当前序列的前半部分继续查找，直到找到相同的元素，或者所查找的序列范围为空为止。
五、{{B}}算法设计题{{/B}}(总题数：1，分数：10.00)
26.已知：typedef struct node{ int data; struct node*next; }LinkNode; typedef LinkNode*LinkList; 请编写原型为int Listisequal(LinkList A, LinkList B)的函数，指针A、B分别指向两个带头结点的单
链表。函数功能是：若单链表A、B中全部对应结点的data值相等，则返回1，否则返回0。
（分数：10.00）
__________________________________________________________________________________________ 正确答案：(intListisequal(LinkListA，LinkListB){ LinkNode*p, *q; p=A; q=B; while(p!=null){ if(p-＞data!=q-＞data)return0; p=p-＞next; q=q-＞next; } return 1;)
解析：[考点] 单链表操作 [解析] 首先定义两个指针p，q分别指向单链表A，B，然后通过p，q依次后移比较当前指向的元素是否相等，一旦出现不相等则返回0，如果比较到最后都相等则返回1。
2012年10月--2007年1月自考2331数据结构历年试题和答案
全国2012年10月高等教育 一、单项选择题(本大题共l5小题，每小题2分，共30分) 1．一个算法的时间耗费的数量级称为该算法的( D ) D．时间复杂度 2．顺序表便于( D ) D．按序号查找结点 3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是( B ) B．p->next==head 4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为( A ) A．(rear-front+m)％m 5．下列关于顺序栈的叙述中，正确的是( A ) A．入栈操作需要判断栈满，出栈操作需要判断栈空 6．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1，每个元素占一个存储单元，则a7,5的地址为( D ) D．34 7．树的后序遍历等价于该树对应二叉树的( C ) C．中序遍历 8．使用二叉线索树的目的是便于( D ) D．查找一个结点的前趋和后继9．设无向图的顶点个数为n，则该图边的数目最多为( B) B．n(n-1)／2 10．可进行拓扑排序的图只能是（Ｃ）C．有向无环图 11．下列排序方法中稳定的是（Ａ）A．直接插入排序 12．下列序列不为 ．．堆的是（Ｃ）C．75,65,30,l5,25,45 13．对线性表进行二分查找时，要求线性表必须是（Ｃ）C．顺序存储且按关键字有序 14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同 ．．的序列是（Ａ）A．(4,1,2,3,5) 15．下列关于m阶B树的叙述中，错误 ．．的是（Ａ）A．每个结点至多有m个关键字二、填空题(本大题共10小题，每小题2分，共20分) 16．数据元素之间的逻辑关系称为数据的__逻辑____结构。 17．在线性表中，表的长度定义为__数据元素的个数____。 18．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到 1、3、4、2的出栈顺序，相应的S和X的操作序列为__ＳＸＳＳＸＳＸＸ____。19．在二叉树中，带权路径长度最短的树称为__哈夫曼树____。 20．已知广义表G，head(G)与tail(G)的深度分别为4和6，则G的深度是_６_____。21．一组字符(a,b,c,d)在文中出现的次数分别为(7，6，3，5)，字符＇d＇的哈夫曼编码的长度为__２____。 22．在一个具有n个顶点的无向图中，要连通全部顶点至少需要__ｎ－１____条边。23．直接选择排序算法的时间复杂度是__Ｏ（ｎ）____。 24．对于长度为81的表，若采用分块查找，每块的最佳长度为___９___。 1 / 29
2011年10月数据结构试题及答案
全国2011年10月高等教育自学考试-----数据结构试题 一、单项选择题（本大题共15小题，每小题2分，共30分） 1、在数据的逻辑结构中，树结构和图结构都是（） A.非线性结构 B.线性结构 C.动态结构 D.静态结构 2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（） A.O（1） B.Ｏ（log n） C.O（n） D.O（n2） 3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（） A.p1－＞next=p2－＞next;p2－＞next=p1－＞next; B. p2－＞next=p1－＞next;p1－＞next=p2－＞next; C. p=p2－＞next; p1－＞next=p;p2－＞next=p1－＞next; D. p=p1－＞next; p1－＞next= p2－＞next；p2－＞next=p; 4.设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为（） A.2个 B.3个 C.4个 D.6个 5.队列的特点是（） A.允许在表的任何位置进行插入和删除 B.只允许在表的一端进行插入和删除 C.允许在表的两端进行插入和删除 D.只允许在表的一端进行插入，在另一端进行删除 6.一个链串的结点类型定义为 ﹟define NodeSize 6 typedef struct node{ char data[NodeSize]; struct node*next; }LinkStrNode; 如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（） A.1/3 B.1/2 C.2/3 D.3/4 7.广义表A=（a,B,(a,B,(a,B,……）））的长度为（） A.1 B.2 C.3 D.无限值 8.已知10×12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1][1] 的存储地址为420，则A[5][5]的存储地址为（） A.470 B.471 C.472 D.473 9.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（） A.12 B.16 C.18 D.20 10.在带权图的最短路径问题中，路径长度是指（） A.路径上的顶点数 B.路径上的边数 C.路径上的顶点数与边数之和 D.路径上各边的权值之和 11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（） A.e B.2e C.n2-2e D.n2-1 12.要以O（n log n）时间复杂度进行稳定的排序，可用的排序方法是（） A.归并排序 B.快速排序 C.堆排序 D.冒泡排序 13.若希望在1000个无序元素中尽快求得前10个最大元素，应借用（） A.堆排序 B.快速排序 1 / 6
2013年山东科技大学考研计算机专业课真题
《数据结构》部分 一、简答题（10分，每题5分） 1、数据元素之间的关系在计算机中的存储有几种表示方法？各有什么特点？ 2、对于堆排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？ 二、应用题（55分） 1、证明：同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同）。（8分） 2、设有正文AADBAACACCDACACAAD，字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。（10分） 3、对于下图完成下列指定操作。（12分） (1)从顶点A出发，求它的深度优先生成树。 (2)从顶点E出发，求它的广度优先生成树。 (3)根据普利姆(Prim) 算法，求它的最小生成树。 4.设哈希(Hash)表的地址范围为0～17，哈希函数为：H (K)=K MOD 16, K为关键字，用线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)构造哈希表，试回答下列问题：（15分） (1) 画出哈希表示意图。 (2) 若查找关键字63，需要依次与哪些关键字比较? (3) 若查找关键字60，需要依次与哪些关键字比较? (4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 5．奇偶交换排序如下所述：对于初始序列A[1]，A[2],…,A[n],第一趟对所有奇数i（1<=i 数据结构真题2013年10月 (总分：100.01，做题时间：90分钟) 一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00) 1.算法的时间复杂度表征的是______ ∙ A.算法的可读性 ∙ B.算法的难易程度 ∙ C.执行算法所耗费的时间 ∙ D.执行算法所耗费的存储空间 （分数：2.00） A. B. C. √ D. 解析：[考点] 算法的时间复杂度定义 [解析] (1)执行算法所耗费的时间，即时间复杂性；(2)执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；(3)算法应易于理解、易于编程、易于调试等，即可读性和可操作性。因此表征算法时间复杂度的是执行算法耗费的时间，C正确。 2.对需要频繁插入和删除结点的线性表，适合的存储方式是______ ∙ A.顺序存储 ∙ B.链式存储 ∙ C.索引存储 ∙ D.散列存储 （分数：2.00） A. B. √ C. D. 解析：[考点] 链式存储方式 [解析] 应该采用链式存储结构。因为采用链式结构存储线性表，插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。但移动指针域操作比移动元素操作花费的时间少得多。 3.在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是______ ∙ A.p-＞next-＞next==head ∙ B.p-＞next==head ∙ C.p-＞next-＞next==NULL ∙ D.p-＞next==NULL （分数：2.00） A. 全国2001年10月高等教育自学考试数据结构试题 课程代码：02331 第一部分选择题(30分) 一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1．算法指的是（） A．计算机程序B．解决问题的计算方法 C．排序算法D．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）A．O（1）B．O（n）C．O（m）D．O（m+n） 4．由两个栈共享一个向量空间的好处是：（） A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率 C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率 5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（） A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 6．如下陈述中正确的是（） A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（） A．O（）B．O（n）C．O（n2）D．O（n3） 8．一个非空广义表的表头（） A．不可能是子表B．只能是子表 C．只能是原子D．可以是子表或原子 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表 0 2 3 3 5 对应的稀疏矩阵是（） 10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A．4 B．5 C．6 D．7 11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A．e B．2e C．n2－e D．n2－2e 第 1 页/共 4 页 考试类别[学生填写]（□正考 □补考 □重修 □补修 □缓考 □其它） 1、以下属于逻辑结构的是（ ） A ）顺序表 B ）散列表 C ）有序表 D ）单链表 2、以下算法的时间复杂度为（ ） void fun(int n){ int i=1; while(i<=n) i=i*2; } A ）O(n) B ）O(n 2 ) C ）O(nlog 2 n) D ）O(log 2 n) 3、若线性表最常用的操作是存取第i 个元素及其前驱和后继元素的值，为了提高效率，应采用（ ）的存储方式。 A ）单链表 B ）双向链表 C ）单循环链表 D ）顺序表 4、设线性表中有2n 个元素，（ ）算法，在单链表上实现要比在顺序表上实现效率更高。 A ）删除所有值为x 的元素 B ）在最后一个元素的后面插入一个新元素 C ）顺序输出前k 个元素 D ）交换第i 个元素和第2n – i – 1个元素的值（i=0，…，n-1） 5、栈和队列的主要区别在于（ ） A ）它们的逻辑结构不一样 B ）它们的存储结构不一样 C ）所包含的元素不一样 D ）插入、删除操作的限定不一样 6、设有一个10阶的对称矩阵A[10][10], 采用压缩存储方式按行优先将矩阵中下三角部分的元素存入一维数组B 中，A[0][0]存入B[0]中，则A[8][5]在B 中的位置是( ) A ）32 B ）33 C ）41 D ）65 7、树最适合用来表示（ ）的数据。 A ）有序 B ）无序 C ）任意元素之间具有多种联系 D ）元素之间具有分支层次关系 8、高度为h 的完全二叉树最少有（ ）个结点。 A ）2h B ）2h +1 C ）2h-1 D ）2h -1 9、假设一个有n 个顶点和e 条边的有向图用邻接表表示，则删除与某个顶点v i 相关的所有边的时间复杂度为（ ） A ）O(n) B ）O(e) C ）O(n+e) D ）O(ne) 10、无向图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 B ）a ，c ，f ，e ，b ，d C ）a ，e ，b ，c ，f ，d D ）a ，e ，d ，f ，c ，b 11、对于顺序存储的有序表（5, 12, 20, 26, 37, 42, 46, 50, 64），若采用折半查找，则查找元素26的查找长度为（ ） A ）2 B ）3 C ）4 D ）5 12、采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（ ） A ）数据元素过多 B ）装载因子过大 C ）散列函数选择不当 D ）解决冲突的方法选择不当 13、若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ） A ）直接插入排序 B ）选择排序 C ）基数排序 D ）快速排序 14、对以下数据序列利用快速排序进行排序，速度最快的是（ ） A ）{21，25，5，17，9，23，30} B ）{25，23，30，17，21，5，9} C ）{21，9，17，30，25，23，5} D ）{5，9，17，21，23，25，30} 15、堆是一种有用的数据结构，下列排序码中序列中，（ ）不是一个堆。 A ）100，85，98，77，80，60，82，40，20，10，66 B ）100，98，85，82，80，77，66，60，40，20，10 C ）10，20，40，60，66，77，80，82，85，98，100 D ）100，85，40，77，80，60，66，98，82，10，20 二、填空题（每空2分，共10分） 下面是折半插入排序算法的实现，请补充完整代码。 void InsertSort(ElemType A[], int len) { int i, j, low, high, mid; for(i=2; i<=len; i++) { A[0]=A[i]; low=1; high=__________; while(__________________) { 线 订 装 郑州轻工业学院2013 — 2014学年 第 1 学期 数据结构 试卷 B 卷 专业年级及班级 姓名 学号 2013年“数据结构与C程序设计”(代码991)试题 一、单项选择题（本题共20分，每小题各2分） 1．对于长度为n的线性表，建立其对应的单链表的时间复杂度为( )。 A．O(1)；B．O(log2n)；．O(n)；D．O(n2)。 2．一般情况下，在一个双向链表中插入一个新的链结点，( )。 A．需要修改4个指针域内的指针；B．需要修改3个指针域内的指针； C．需要修改2个指针域内的指针；D．只需要修改1个指针域内的指针。 3．假设用单个字母表示中缀表达式中的一个运算数(或称运算对象)，并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*(C/D-E)，当从左至右扫描到运算数E时，堆栈中的运算符依次是( )。(注：不包含表达式的分界符) A．+*/-；B．+*(/-；C．+*-；．+*(-。 4．若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70，则后序遍历序列为( )。 A．30,40,20,50,70,60,80；B．30,40,20,70,60,80,50； C．70,60,80,50,30,40,20；D．70,60,80,30,40,20,50。 5．分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼(Huffman) 树的深度为( )。 A．6；B．5；C．4；D．3。 6．下列关于图的叙述中，错误的是( )。 A．根据图的定义，图中至少有一个顶点； B．根据图的定义，图中至少有一个顶点和一条边(弧)； C．具有n个顶点的无向图最多有n(n-1)/2条边； D．具有n个顶点的有向图最多有n(n-1)条边(弧)。 7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是( )。 A．G中有弧 自考数据结构02331历年试题及答案(2009--2018个人整理版) 全国2009年1月自学考试数据结构试题 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列程序段的时间复杂度为( )9 s=0； for(i=1；i 西安电子科技大学 考试时间 120 分钟 试题（A） 题号一二三四五六七八九十总分 分数 1.考试形式：闭卷；2。考试日期：2013年月日3.本试卷共四大题，满分100分。 班级学号姓名任课教师 一、单选题（15小题，每题2分，共30分） 1. 以下关于数据结构的描述正确的是（B ） A．数据的逻辑结构描述了数据项与数据项之间存在的某种关系 B．数据结构操作的实现与存储结构有关 C．数据的逻辑结构相同，对应的存储结构也相同 D．数据结构的抽象数据类型中操作的定义与存储结构有关 2. 关于算法的时间复杂度的描述正确的是（C ） A．时间复杂度相同的算法在相同的计算机上的运行时间相同 B．时间复杂度相同的算法在解决问题的规模相同时运行时间相同 C．算法的时间复杂度仅反映算法的运行时间与问题规模之间的关系 D．算法的时间复杂度与问题的规模和计算机硬件的运行速度相关 3. 在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（B ） A．O(n) B．O(1) C．O(n2) D．O(log2n) 4. 已知单链表中结点*q是结点*p的直接前驱，若在*q与*p之间插入结点*s，需要执行的操作是（ A ） A．s->next= q->next; q->next=s; B．s->next=p->next; p->next=s; C．q->next=s; s->next= q->next; D．p->next=s; s->next=q; 5. 下列哪种操作利用到了栈的结构（A ） A．递归函数调用B．树的层次遍历 C．顺序查找D．选择排序 6．设有一个n×n的对称矩阵A的下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A中的元素A[i][j]存放于B中的存放位置是（A ） A．(i+1)*i/2+j B．(i+1)*j/2+j 10月自考数据结构02331试题及答案解析 10月自考数据结构02331试题及答案解析 lO月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共8页。满分l00分。考试时间l50分钟。考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸. 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间．超出答题区域无效。 第一部分选择题 一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡” 的相应代码涂黑。未涂、错涂或多涂均无分。1．下列选项中，不属于线性结构的是 A．网 B．栈 C．队列D．线性表 2．长度为n的顺序表，删除位置i上的元素 (0≤i≤n一1)，需要移动的元素个数为 A．n—i B．n—i—l C．i D．i+1 3．栈采用不同的存储方式时，下列关于出栈过 程的叙述中，正确的是 A．顺序栈需要判定栈空，链栈也需要判定 B．顺序栈需要判定栈空，而链栈不需要判定 C．顺序栈不需要判定栈空，而链栈需要判定 D．顺序栈不需要判定栈空，链栈也不需要判 定 4．若一个栈以数组V[0．．n-1]存储，初始栈顶 指针top为n，则x入栈的正确操作是 A．top=top+1；V[top]=x B．V[top]=x；top=top+1 C．top=top一1；V[mp]=x D．V[top]=x；top=top—l 5．在二维数组a[9][10]中：每个数组元素占用 3个存储空间，从首地址SA开始按行优先 连续存放，则元素a[8][5]的起始地址是 A．SA+141 B．SA+144 C．SA+222 D．SA+255 6．广义表A=(x，((y)，((a))，A))的深度是 A．2 B．3 C．4 D．∞ 7．一棵左子树为空的二叉树在前序线索化后， 其空指针域个数为 A．0 B．1 C．2 D．不确定 8．下列关于哈夫曼树的叙述中，错误的是 A．用n个结点构造的哈夫曼树是唯一的 B．哈夫曼树中只有度为0或度为2的结点 C．树中两个权值最小的结点可能是兄弟结点 D．同一结点集构造的二叉树中，哈夫曼树的 WPL最小 9．6个顶点的强连通图中，含有的边数至少是 A．4 B．5 C．6 D．7 10．对题l0图进行深度优先搜索遍历，下列选 项中，正确的遍历序列是 12．有向图采用邻接矩阵存储，某一行中非零元素的个数等于A．对应顶点v的度 全国2010年10月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据的四种存储结构是( ) A-P3 A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下 列选项中，应选择的存储结构是( ) D-P26（带尾指针） A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D.带头结点的单循环链表 3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( )C P22 A.head=NULL B.head->next=NULL C.head!=NULL D.head->next!=head 4.若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是( )D A.n-i B.n-i+l C.n-i+2 D.无法确定 5.串匹配算法的本质是( ) C P55 A.串复制 B.串比较 C.子串定位 D.子串链接 6.设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节 空间，则a85的地址为( ) C P61 A.13 B.18 C.33 D.40 7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) B A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) A A.n B. C. +1 D.n/2 9.在图G中求两个结点之间的最短路径可以采用的算法是( )A P123 A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 绝密★考试结束前 全国2013年10月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．算法的时间复杂度表征的是 A．算法的可读性B．算法的难易程度 C．执行算法所耗费的时间D．执行算法所耗费的存储空间 2．对需要频繁插入和删除结点的线性表，适合的存储方式是 A．顺序储存B．链式存储 C．索引存储D．散列存储 3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是 A．p->next->next==head B．p->next==head C．p->next->next==NULL D．p->next==NULL 4．迪杰斯特拉(Dijkstra)算法的功能是 A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径 C．求图的最小生成树D．求图的拓扑排序序列 5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能 ．．．获得的出栈序列是 A．4，5，3，2，1 B．4，3，5，1，2 C．1，2，3，4，5 D．5，4，3，2，1 6．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为 A．1015 B．1016 全国2019年10月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在 题干的括号内。每小题2分，共30分) 1.计算机识别、存储和加工处理的对象被统称为( ) A.数据 B.数据元素 C.数据结构 D.数据类型 2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 ( ) A.O(1) B.O(n) C.O(nlogn) D.O(n2) 3.队和栈的主要区别是( ) A.逻辑结构不同 B.存储结构不同 C.所包含的运算个数不同 D.限定插入和删除的位置不同 4.链栈与顺序栈相比，比较明显的优点是( ) A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况 5.采用两类不同存储结构的字符串可分别简称为( ) A.主串和子串 B.顺序串和链串 C.目标串和模式串 D.变量串和常量串 6.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的 结果是( ) A.0 B.2 C.3 D.5 7.已知广义表的表头为a，表尾为(b,c)，则此广义表为( ) A.(a,(b,c)) B.(a,b,c) C.((a),b,c) D.((a,b,c)) 8.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址 为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为( ) A.470 B.471 C.472 D.473 9.二叉树中第5层上的结点个数最多为( ) A.8 B.15 C.16 D.32 10.下列编码中属前缀码的是( ) A.{1,01,000,001} B.{1,01,011,010} C.{0,10,110,11} D.{0,1,00,11} 11.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是( ) 1 全国 2019 年 10 月高等教育自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题（本大题共15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列说法正确的是（） A．数据是数据元素的基本单位 B．数据元素是数据项中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成 2．数据结构的基本任务是（） A．逻辑结构和存储结构的设计B．数据结构的运算实现 C．数据结构的评价与选择D．数据结构的设计与实现 3．在一个具有 n 个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作 的时间复杂性量级为（） A． O（ 1）B． O（ n） 2 D． O(n 2 ) C． O（ nlog n） 4．顺序存储的线性表（a1,a2,,a n） ,在任一结点前插入一个新结点时所需移动结点的平均 次数为（） A． n B． n/2 C． n+1D． (n+1)/2 5．下列树U ′，经剪技运算DELETE （ U ′， x， 2）后为（） 6．一棵有16 结点的完全二叉树，对它按层编号，则对编号为7 的结点 X ，它的双亲结点及右孩子结点的编号分别为（） A． 2，14B． 2， 15 C． 3， 14D． 3， 15 7．设有一 5 阶上三角矩阵 A ［ 1..5， 1..5］，现将其上三角中的元素按列优先顺序存放在一 1 堆数组 B［ 1..15 ］中。已知 B［ 1］的地址为100，每个元素占用 2 个存储单元，则A［3，4］的地址为（） A． 116B． 118 C． 120D． 122 8．一个带权的无向连通图的最小生成树（） A．有一棵或多棵B．只有一棵 C．一定有多棵D．可能不存在 9．下列有关图遍历的说法中不正确的是（） A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（） A．小于顺序表的平均查找长度B．大于顺序表的平均查找长度 C．与顺序表的平均查找长度相同D．无法与顺序表的平均查找长度比较 11．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（） A．同义词之间发生冲突引起的 B．非同义词之间发生冲突引起的 C．同义词之间或非同义词之间发生冲突引起的 D．散列表“溢出”引起的 12．从外存设备的观点看，存取操作的基本单位是（） A．逻辑记录B．数据元素 C．文件D．物理记录 13．对文件进行检索操作时，每次都要从第一个记录开始的文件是（） A．顺序文件B．索引文件 C．顺序索引文件D．散列文件 14．一组记录的键值为（46， 74， 18， 53，14， 20，40， 38， 86， 65），利用堆排序的方法 建立的初始堆为（） A．（ 14， 18， 38， 46， 65， 40， 20，53， 86，74） B．（ 14，38， 18，46， 65， 20， 40， 53， 86， 74） C．（ 14，18， 20，38， 40， 46， 53，65， 74，86） D．（ 14， 86， 20， 38， 40， 46， 53，65， 74，18） 15．对序列（ 22， 86， 19， 49， 12， 30， 65， 35， 18）进行一趟排序后得到的结果如下：（18， 12，19， 22，49， 30， 65， 35，86），则可以认为使用的排序方法是（）A．选择排序B．冒泡排序 C．快速排序D．插入排序 二、填空题（本大题共13 小题，每空 2 分，共 26 分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、 _______________和散列存储方式。 2 2013年韩山师范学院本科插班生考试试卷 计算机科学与技术专业数据结构试卷（A卷） 一、单项选择题（每题1.5分，共30分） 1、数据的不可分割的最小单位是（）。 A．数据元素 B．数据对象 C．数据项 D．数据串 2、一个算法应该具有一些重要特性，下列不是算法特性的是（）。 A．有穷性 B．确定性 C．可行性 D．健壮性 E．至少一个输出 3、下面关于线性表的表述中，（）是错误的？ A．若线性表采用顺序存储，必须占用一片连续的存储单元。 B．若线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，占用的存储单元不一定是连续的。 D．线性表采用链接存储，便于插入和删除操作。 4、下列哪个不是链表所具有的特点是（）。 A．可随机访问表中元素B．插入、删除不需要移动元素 C．线性链表必须有一个指针域D．所需空间与线性长度成正比 5、若线性表的长度为 n，且采用顺序存储结构，则等概率删除其第 i个元素的算法的时间 复杂度为（）(1<=i<=n)。 A. O(i) B. O(n-i) C. O(1) D. O(n) 6、静态链表中指针表示的是（）。 A．内存地址 B．数组下标 C．表头地址 D．下一元素地址 7、下列关于串的叙述中正确的是。 A．串中所含的字母个数称为串的长度B．串是一种特殊的线性表 C．串中的字母不区分大小写D．由空格组成的串称为空串 的存储地址8、设有一个采用压缩存储的9 阶对称矩阵A，以行序为主存储，第一个元素a 11为 0，每个元素占一个地址空间，则a 的地址为（）。 86 A. 26 B. 27 C. 36 D. 37 E.46 F.47 9、判断一个带表头的循环链表H为空表的判定条件是（） A.H＝＝NULL B.H->next==NULL C.H->next＝NULL D.H－>next==H 10、若一个栈的输入序列为 1,2,3,…,n，输出序列的第一个元素是 i，则第 j 个输出元素 全国2013年10月自学考试数据库系统原理试题及答案 课程代码：04735 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1．答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2．每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。未涂、错涂或多涂均无分。 1．在数据管理技术发展过程中，关于数据库阶段描述错误 ．．的是（C） A．采用数据模型表示复杂的数据结构B．有较高的数据独立性 C．对数据的操作只能以记录为单位D．数据库系统为用户提供了方便的用户接口 2．关于逻辑模型，下面叙述错误 ．．的是（A） A．逻辑模型独立于硬件和软件 B．逻辑模型表达了DB的整体逻辑结构 C．逻辑模型是从数据库实现的观点出发，对数据建模 D．逻辑模型是数据库设计人员与应用程序员之间交流的工具 3．对于数据库系统生存期，属于数据库实现阶段的工作的是（B） A．将局部概念模型综合成全局概念模型 B．数据库试运行 C．设计应用程序与数据库的接口 D．数据库的重组织和重构造 4．在关系模型完整性规则中，要求“不允许引用不存在的实体”的规则是（B） A．实体完整性规则B．参照完整性规则 C．用户定义的完整性规则D．域的引用规则 5．已知关系R有如下函数依赖{AB→C,BC→D,AD→E}，则{A，B}的闭包是（D） A．{A，B} B．{A，B，C} C.{A,B,C,D} D.{A,B,C,D,E} 6．关于关系模式分解，叙述正确的是（C） A.2NF的关系模式不一定是1NF B.3NF的关系模式一定是BCNF C．分解成BCNF模式集的算法能保证无损分解，但不一定能保证FD集 D．消除了非主属性对键的局部函数依赖的关系一定是3NF 7．有关系SC(SNO,CNO,AGE,SCORE)，查找年龄大于22岁的学生的学号和分数，正确的关系代数表达式是（A） 2012年10月全国自考软件工程模拟试题和答案(二) 一、单项选择题(本大题共20小题，每小题1分，共20分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1. 软件管理比其他工程管理更为() A. 容 易 B. 困 难 C. 迅 速 D. 迟 缓 答案：B 2. 以下说法错误的是() A. McCabe度量法对于不同种类的控制流的复杂性 不能区分 B. McCabe度量法将简单IF语句与循环语句的复杂性 分别看待 C. McCabe度量法对于嵌套IF语句与简单CASE语句的复杂性 是一样的 D. McCabe度量法将模块接口当成一个简单分支 一样处理 答案：B 3. 早期的软件工具只能完成一件特定的任务，后来出现了工作台，它将一组工具 组合在一起 ，对软件开发过程的某些方面提供支持。()是工作台的发展，其目的在于为软件开发提供完整的 和一致的支持。 A. 软件开发环 境 B. 软 件 C. 工 具 D. 工作 台 答案：A 4. 表示连接的系统流程图的符号是() A. A B. B C. C D. D 答案：B 5. Jackson方法是一种面向()的方法。 A. 对象 B. 数据结构 C. 数据流 D. 控制流 答案：B 6. IDEF图从各个侧面反映系统() A. 怎么做 B. 做什么 C. 对谁做 D. 何时做 答案：B 7. 需求规格说明书的作用不应包括() A. 软件设计的依据 B. 用户与开发人员对软件要做什么的共同理解 C. 软件验收的依据 D. 软件可行性研究的依据 答案：D 8. 以下说法错误的是() A. MTTF是一个描述失效模型或一组换效特性的指标量 B. MTBF是指两次相继失效之间的平均时间 C. MTBF在实际使用时通常指当n很大时，系统第n次失效与第n+1次失效之间 的平均时间 D. 对于失效率为常数和修复时间很短的情况，MTTF与MTBF差别很大 答案：D 9. 在软件结构设计的后处理中，下列说法错误 的是() A. 为模块写的处理说明及接口说明 可采用IPO图B. 数据结构的描述可用 Warnier图或Jackon图 C. 给出设计约束或限制。如数据的边界值，数据类型、格式、内存容量及时间 的限 D. 设计的优化工作主要放在软件结构设计的后处理阶段 答案：D 10. 以下说法错误的是() A. GB指中华人民共和国国家军用标准 B. ANSI指美国国家标准协会 C. BS指英国国家标准 D. DIN指德国标准协会 答案：A数据结构真题2013年10月
全国2001年10月高等教育自学考试数据结构试题
数据结构2013试题B卷
北航数据结构与程序设计真题 2013年北航991真题及答案
自考02331数据结构真题及答案(2009-2018)
2013 数据结构试题 (答案)
10月自考数据结构02331试题及答案解析
数据结构(代码02331)2010年10月试题及答案
02331数据结构2013年10月份历年真题附答案
10月全国数据结构自考试题及答案解析
10月全国数据结构导论自考试题及答案解析
2013年韩山师范学院本科插班生《数据结构》试卷
全国2013年10月自学考试数据库系统原理试题及答案
2013年10月全国自考软件工程模拟试题
- 2013年算法与数据结构文档.doc
- E__Temp2_2013数据结构试题
- 02142数据结构导论2013年10月份真题及答案
- 数据结构复习答案2013-1
- 院校资料-北京理工大学2013级数据结构B试题(A卷)-答案
- 数据结构真题2013年10月
- 2013年算法与数据结构文档
- 02331数据结构 全国13年10月自考 试题
- 02331数据结构2012年10月份历年真题02331数据结构2013年1 月份历年真题附答案
- 数据结构课件(2013年)zy (1)
- 2013数据结构 学生信息管理系统-大二
- 2013年数据结构试题集(10套题并附带答案)
- 2013年数据结构试题集10套题并附带答案
- 数据结构(本)期末综合练习(2013年12月)
- 2013年暨南大学830数据结构考研试题
- [考试必备]2013年深圳大学801数据结构考研试题
- 真题_2013年_数据结构
- 数据结构教程图2013
- 2012-2013数据结构
- 2013年10月自学考试数据结构导论试题及答案