题号 一 二 三 四 五 六 七 八 九 总 分 得分
一、单项选择题（本大题共12小题，每小题2分，共24分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。选错、多选或未选均无分。
1.按值可分解，数据类型通常可分为两类，他们是 【 C 】 A．静态类型和动态类型 B. 原子类型和表类型 C．原子类型和结构类型 D. 数据类型和指针类型 2.对于三个函数f(n)=2008
+8
+96000，g(n)=8
+8n+2008和
h(n)=8888nlogn+3n2，下列陈述中不成立的是 【C 】
A. f(n)是O(g(n)) B. g(n)是O(f(n))
C. h(n)是O(n
)
D. h(n)是O(
)
3.指针p、q和r依次指向某循环链表中三个相邻的节点，交换节点*q和
节点*r在表中的次序的程序段是 【 A 】 A. p->next=r; q->next=r->next; r->next=q;
B. p->next=r; r->next=q; q->next=r->next; C. r->next=q; q->next=r->next; p->next=r;
D. r->next=q; p->next=r; q->next=r->next; 4.若进栈次序为 a ,b ,c,且进栈和出站可以穿插进行，则可能出现的含个元素的出站序列个数是 【 B 】 A．3 B．5 C．6 D．7
5.假设以数组A[n]存放循环队列的元素，其头指针front指向队头元素的前一个位置、为指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 【 D 】 A．rear==front B. (front+1)%n==rear
C. rear+1==front D.(rear+1)%n==front 6.串的操作函数str定义为： int str (char *s) { char *p=s; while (*p!=’\\0’) p++; return p-s; }
则str(“abcde”)的返回值是 【 C 】 A．3 B．4 C．5 D．6 7.二维数组A[10][6]采用行优先的存储方法，若每个元素占4个存储单元，已知元素A[3][4]的存储地址为1000，则元素A[4][3]的存储地址为 【 A 】 A．1020 B．1024 C．1036 D．1240 8.对广义表L=(a,())执行操作tail(L)的结果是 【 B 】 A．() B．(()) C．a D．(a) 9.已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为 【 A】 A. FEDCBA B. ABCDEF C. FDECBA D. FBDCEA 10.已知森林F={,
,,,
},各棵树(i=1，2，3，4，5)中所含节点
的个数分别为7，3，5，1，2，则与F对应的二叉树的右子树种的节点个
数为 【 D 】 A．2 B．3 C．8 D．11 11.若非连通无向图G含有21条边，则G的顶点个数至少为 【 B 】 A．7 B．8 C．21 D．22 12.如图所示的有向图的拓扑序列是 】 【 B a b A. c , d , b , a , e B. c , a , d , b , e C. c , d , e , a , b e D. c , a , b , d , e c d 题12图
１
二、填空题(本大题7小题，每题2分，若有两个空，每个空格1分，共
14分)请在每个空格中填上正确答案。错填、不填均无分。
1.数据的链式存储结构的特点是借助 指示元素存储地址的指针
表示数据元素之间的逻辑关系。
2.如果需要对线性表频繁进行 插入 或 删除 操作，则不宜采用顺序存储结构。
3.如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n+1，则“栈满”的判定条件是 top1=top2+1 top1 。 top2 0 n-1
栈1 栈2
4.静态存储分配的顺序串在进行插入、置换和 连接 等操作时可能发生越界。
5.广义表L=(a，(b，()))的深度为 3 。
6.任意一棵完全二叉树中，度为1的节点数最多为 1 。
7.求最小生成树的克鲁斯卡尔算法耗用的时间与图中 边 的数目
正相关。
三、解答题（本大题共4小题，每小题8分，共24分） 1.如图所示，在nn矩阵A中，所有下标值满足关系式i+j p=8 （2）设元素 存储在sa[k]中，写出有i,j和n计算k的一般公式。 题3-1图 k=i(i-1)/2+j+i-n-1 2.由字符集{s，t，a，e，i}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。 0 1 0 1 0 1 t i e 0 1 a s eatst 题3-2图 3.已知无向图G的邻接表如图所示， （1）画出该无向图； （2）画出该图的广度优先生成森林。 0 A 1 2 3 ∧ 1 B 0 2 ∧ 3 4 5 ∧ 2 C 0 1 3 D 0 2 ∧ 4 E 2 5 ∧ 5 F 2 4 ∧ 6 G 7 8 ∧ 7 H 6 8 ∧ 8 I 6 7 ∧ 题3-3图 ２ 四、算法阅读题（本大题共3小题，每题8分，共24分） 1.阅读下列算法，并回答问题： （1） 无向图G如图所示，写出算法f30(&G)的返回值； k=3 （2）简述算法f30的功能。 B A G C D F H 求图中连通分量的数目 #define MaxNum 20 int visited[MaxNum]; void DFS(Graph *g, int i); /*从顶点出发进行深度优先搜索，访问顶点时置visited[j]为1*/ int f30(Graph *g) { Int i,k; for (i=0;I < g->n; i++) /*g->n为图g的定点数目*/ visited[i]=0; for (i=k=0; I < g->n; i++) if (visited[i]==0) { K++; DFS(g,i); } return k; } 2.假设学生成绩按学号增序从年初在带头结点的单链表中，类型定义如下： typedef struct Node{ int id; /*学号*/ int score; /*成绩*/ struct Node *next; }LNode, *LinkList; 阅读算法f31，并回答问题； （1）设节点结构为id score next ,成绩链表A和B如图所示，画 出执行算法f31(A,B)后节点A所指的链表； A 1 70 2 40 3 90 4 48 5 56 B 2 38 4 65 5 75 题31图 （2）减速算法f31的功能。 Void f31(LinkList A, LinkList B) { LinkList p,q; p = A->next; q = B->next; while (p && q) { if(p->id < q->id) ３ p = p ->next; else if(p->if > q-> id) q =q –>next; else { if (p->score < 60) if(q->score <60) p->score = q->score; else p->score = 60; p = p->next; q = q->next; } } } 3.阅读下列算法，并回答问题： （1）设串s=“OneWorldOneDream”，t=“One”，pos是一维整型数组，写出算法f32(s,t,pos)执行之后得到的返回值和pos中的值； （2）简述算法f32的功能。 int str(char *s); /*返回串s的长度*/ int index(char *st, char *t); /*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1*/ int f32(char *s, char *t, int pos[]) { int i,j,k,ls,lt; ls = strlen(s); lt = strlen(t); if(ls == 0|| lt==0) return -1; k=0; i=0; do{ j=index(s+I,t); if(j>=0) { Pos[k++]=i+j; I + = j + lt ; } }while (i+lt <= ls && j>=0); Return k; } 五、算法设计题（本题14分） 34.假设线性表采用顺序存储结构，其类型定义如下： #define ListSize 100 typedef struct{ int data[ListSize]; int length; }SeqList, *Table; 编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。 ４ ５ 因篇幅问题不能全部显示，请点此查看更多更全内容