发布时间 : 星期四 文章数据结构历年真题更新完毕开始阅读6ca4bb63caaedd3383c4d321
}
} else { }
pb = pb -> next; (2) ; q = pb; pb = pb -> next; free (q);
if (pb) } (1) (2) (3)
31．已知串的存储结构为动态存储分配的顺序串。阅读下列算法，并回答问题： （1）写出执行函数调用 strc (s, r)的返回结果，其中s=〃aba〃, r=〃abababa〃; （2）简述函数strc的功能。
int strc (HString * sub, HString * str) {
int i=0, j, k, count =0;
while (i < str -> length – sub -> length +1) {
j=i; k=0;
while (k length && str -> ch[j] = =sub -> ch[k] ) {
j++; k++; }
if (k = = sub -> length)
{count ++; i=j-sub -> length +1;} else i++; }
return count; } (1) (2)
32．下列函数MDFSForest的功能是，对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历，输出所得深度优先生成森林中各条边。请在空缺处填入合适内容，使其成为一个完整的算法。 #define MaxMun 20 //图的最大顶点数 typedef struct {
char vexs [MaxNum]; //字符类型的顶点表 int edges [MaxNum][MaxNum]; //邻接矩阵 int n, e; //图的顶点数和边数
25
(3) ;
全国2001年10月自考数据结构试题
}MGraph; //图的邻接矩阵结构描述 typedef enum {FALSE, TRUE} Boolean; Boolean visited [MaxNum];
void MDFSTree (MGraph *G, int i); void MDFSForest (MGraph *G) { int i, k;
for (i=0; i
visited [i] = (1) ; for (k = 0; k
}
void MDFSTree (MGraph *G, int i) { int j;
visited [i]=TRUE; for (j=0; j
if ( (2) ) {
printf (〃<%c, %c>〃G -> vexs [i], G -> vexs [j]); (3) ; } } ｝ （1） （2） （3）
33．已知整形数组L［1..8］中的元素依次为（9，8，5，7，6，3，2，1），阅读下列函数，并写出执行函数调用8)时，对L进行的头两趟（pass分别为0和1）处理结果。 Void sort (int R[],int n) {
int pass = 0, k, exchange, x; do { k=pass%2+1; exchange = 0; while (k if (R[k]>R[k+1]) { x = R[k]; R[k] = R[k+1]; R[k+1] = x; 全国2001年10月自考数据结构试题 sort(L, 26 } exchange =1; K+=2 } } 第一趟（pass = 0）: 第二趟（pass = 1）: 五、算法设计题（本大题共10分） 34．已知二叉排序树中结点的关键字为整数，设计递归算法按递增有序性输出树中所有大于或等于给定值x的结点，并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构，其结点结构为： lchild key rchild pass ++; }while (exchange = = 1|| pass <=1); 全国2005年1月高等教育自学考试 一、单项选择题(本大题共15小题，每小题2分，共30分) 1.数据元素及其关系在计算机存储器内的表示，称为数据的( ) A.逻辑结构 B.存储结构C.线性结构 A.head==NULL D.非线性结构 2.某带头结点的单链表的头指针为head，判定该链表为非空的条件是( ) B.head->next==NULLC.head!=NULL D.head->next!=NULL D.栈空时执行的入栈 3.导致栈上溢的操作是( ) A.栈满时执行的出栈B.栈满时执行的入栈C.栈空时执行的出栈 4.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是( ) A.(rear-front)%m= =1B.front= =rearC.(rear-front)%m= =m-1 D.front= =(rear+1)%m 5.假设S=″I AM A STUDENT″，则运算substr(S,4,8)的结果为( ) A.″M A S″ B.″M A STUD″C.″A STUDEN″ D.″STUD″ 6.在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为( ) A.模式串的最末字符B.主串的第一个字符C.模式串的第一个字符D.主串的最末字符 7.从广义表L=(((d),c,d))中分解得到(d)的操作为( ) A.head(head(head(L))) B.head(tail(head(L)))C.tail(head(head(L))) 子，则左孩子存放在( ) A.BT[i/2] 9.右图所示二叉树的中序序列是( ) A.DHEBAFIJCG B.DHEBAFJICG 全国2001年10月自考数据结构试题 27 D.tail(tail(head(L))) 8.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩 B.BT[2*i-1]C.BT[2*i] D.BT[2*i+1] C.DBHEAFCJIG D.DBHEAFJICG 10.连通图是指图中任意两个顶点之间( ) A.都连通的无向图 B.都不连通的无向图 C.都连通的有向图 D.都不连通的有向图 11.下图所示带权无向图的最小生成树的权为( ) A.14 B.15 C.17 D.18 12.对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为( ) A.123，145，298，314，486，508 B.508，314，123，145，486，298 C.486，314，123，145，508，298 D.298，123，508，486，145，314 13.在待排关键字序列基本有序的前提下，效率最高的排序方法是( ) A.直接插入排序 B.快速排序C.直接选择排序 D.归并排序 14.在下列各棵二叉树中，二叉排序树是( ) 15.采用ISAM或VSAM组织的文件是( ) A.索引非顺序文件 B.顺序文件C.索引顺序文件 D.散列文件 二、填空题 16.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为______。 17.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是______。 18.如果入栈序列是1，3，5，?，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为______。 19.已知广义表LS为空表，则其深度为______。 20.假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，且每个元素占2个存储单元，则A[4][3][2]的地址是______。 21.已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则它的后序序列为______。 22.在含n个顶点的连通图中，任意两个不同顶点之间的一条简单路径最多包含______条边。 23.对关键字序列(50，34，92，19，11，68，56，41，79)进行直接插入排序，当将第7个关键字56插入到当前的有序子表中时，为寻找插入位置需进行______次关键字之间的比较。 24.对有序表进行二分查找的过程可用判定树来描述，其判定树的形态只取决于______。 全国2001年10月自考数据结构试题 28