发布时间 : 星期六 文章数据结构历年真题更新完毕开始阅读6ca4bb63caaedd3383c4d321
}
return degree; } (1) (2) (3)
33.已知单链表的结点结构为 data next
下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。 请在空缺处填入合适的内容，使其成为完整的算法。 void SelectSort(LinkedList L) {
LinkedList p,q,min; DataType rcd; p= (1) ; while(p!=NULL) { min=p; q=p->next;
while(q!=NULL){
if( (2) )min=q; q=q->next; }
if( (3) ){ rcd=p->data;
p->data=min->data; min->data=rcd; }
(4) ; } } (1) (2) (3) (4)
五、算法设计题(本题10分)
34.设线性表A=(a1,a2,a3,?,an)以带头结点的单链表作为存储结构。编写一个函数，对A进行调整，使得当n为奇数时
A=(a2,a4,?,an-1,a1,a3,?,an)，当n为偶数时A=(a2,a4,?,an,a1,a3,?,an-1)。
全国2004年1月高等教育自学考试
一、单项选择题
1．在数据结构中，数据的逻辑结构可以分成（ ） A．内部结构和外部结构
B．线性结构和非线性结构 D．动态结构和静态结构 B．数据元素在表中的序号表示
21
C．紧凑结构和非紧揍结构 A．数据元素的相邻地址表示
2．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）
全国2001年10月自考数据结构试题
C．指向后继元素的指针表示 D．数据元素的值表示
3．设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（ ） s -> next = p -> next; p -> next = s;
t = p -> data; p -> data = s -> data; s ->data = t;
A．结点*p与结点*s的数据域互换B．在p所指结点的元素之前插入元素 C．在p所指结点的元素之后插入元素D．在结点*p之前插入结点*s 4．栈和队列都是（ ） A．限制存取位置的线性结构 C．链式存储的线性结构
B．顺序存储的线性结构 D．限制存取位置的非线性结构
5．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为 A．1和n+1
B．1和n/2C．－1和n
D．－1和n+1
6．执行下列程序段后，串X的值为（ ）
S=〞abcdefgh〞; T=〞xyzw〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y);
B．〞cdxyzw〞C．〞cdefxy〞 D．〞cdefef〞
B．数组的元素必须从左到右顺序排列 D．数组是多维结构，内存是一维结构
D．tail (tail (head (LS)))
A．〞cdefgh〞
7．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（ ） A．数组的元素处在行和列两个关系中 C．数组的元素之间存在次序关系
8．从广义表LS＝（(p, q), r, s）中分解出原子q的运算是（ ） A．tail (head (LS)) B．head (tail (head (LS)))C．head (tail (LS)) A．2n+1
B．2nC．2n-1
D．2n-2
9．在具有n个叶子结点的严格二叉树中，结点总数为（ ） 10．若
B．vj邻接于viC．vi和vj相互邻接 D．vi与vj不相邻接
B．深度优先生成树中 D．深度优先生成森林中
11．在一个带权连通图G中，权值最小的边一定包含在G的（ ） A．最小生成树中 C．广度优先生成树中
12．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ ）
A．左子树的叶子结点 B．左子树的分支结点C．右子树的叶子结点 D．右子树的分支结点 13．希尔排序的增量序列必须是（ ） A．递增的
B．随机的C．递减的
D．非递减的
14．如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（ ） A．插入排序
B．归并排序C．冒泡排序
D．堆排序
D．顺序文件
15．设置溢出区的文件是（ ） A．索引非顺序文件
B．ISAM文件C．VSAM文件
二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
22
全国2001年10月自考数据结构试题
16．下列程序段的时间复杂度为________________。 product = 1; for (i = n;i>0; i--) for (j = i+1; j 17．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是________________。 18．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________。 19．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________________。 20．右图表示的广义表为________________。 21．若一棵满三叉树中含有121个结点，则该 树的深度为________________。 22．若以邻接矩阵表示有向图，则邻接矩阵上 第i行中非零元素的个数即为顶点vi的________________。 23．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用________________排序方法。 24．在含20个关键字的3阶B树（2－3树）上查找一个关键字，至多需要访问___________次外存。 25．文件上的两类主要操作为________________和________________。 三、解答题（本大题共4小题，每小题5分，共20分） 26．设栈S1的入栈序列为1 2 3 4（每个数字为13个元素），则不可能得到出栈序列3142。但可通过增设栈S2来实现。例如，按下图中的箭头指示，依次经过栈S1和S2，便可得到序列3 1 4 2。 如果用H1和H2分别表示栈S1和S2的进栈操作，用P1和P2分别表示两个栈的出栈操作，则得到3 1 4 2的一个操作步骤为 H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2 请仿照上例写出利用两个栈从1 2 3 4得到4 1 3 2的操作步骤。 27．已知树如右图所示， （1）写出该树的后序序列； （2）画出由该树转换得到的二叉树。 全国2001年10月自考数据结构试题 23 28．为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是 hi = (h(key) + i(key%5+1))%7 0≤i≤6 （1）画出构造所得的散列表； （2）求出在等概率情况下查找成功时的平均查找长度。 29．已知R［1..8］中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC 对R进行自顶向下的二路归并排序过程中，前5次调用函数Merge(R, low, mid, high)时参数 low, mid 和high的值。 void MergeSortDC (int R[], int low, int mid, int high ) { int mid; if (low } // MergeSortDC （1）第一次调用时的参数值； （2）第二次调用时的参数值； （3）第三次调用时的参数值；（4）第四次调用时的参数值；（5）第五次调用时的参数值； 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb) { //本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd) { if (pa -> data (1) ; pre = pb; 24 mid = (low +high)/2; MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high); Merge (R, low, mid, high); 全国2001年10月自考数据结构试题