2001年10月至2006年10月（自考数据结构试题和答案）课程代号：02331

(3)双向链表(可以:p->prior->data<->p->data;)

27.假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。

(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；

(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。

28.当采用邻接表作为图的存储结构时，也可将邻接表中的顶点表由顺序结构改为链表结构。 (1)请分别画出这种邻接表的顶点链表结点和边表结点，并说明结点中各个域的作用； (2)对如图所示的有向图画出这种邻接表。

29.已知4阶B-树如图所示。

(1)分别画出将关键字23和89相继插入之后的B-树。 (2)画出从插入之前的B-树中删除关键字51之后的B-树。 四、算法阅读题(每小题5分，共20分) 30.阅读下列函数algo,并回答问题：

(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；

(2)简述算法algo的功能。 void algo(Queue *Q) {

Stack S; InitStack(&S);

while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) ＥnQueue(Q,Pop(&S)); } (1)87542 (2) 队列倒置

31.阅读下列函数F，并回答问题：

(1)已知如图所示的二叉树以二叉链表作存储结构，rt为指向根结点的指针。写出执行函数调用F(rt)的输出结果。 (2)说明函数F的功能。 void F(BinTree T) {

Stack S; if(T) {

InitStack(&S); Push(&S,NULL); while(T) {

printf(\

if(T->rchild) Push(&S,T->rchild); if(T->lchild)T=T->lchild; else T=Pop(&S); } } } (1)

(2)前序遍历二叉数 vertex firstedge

32.已知邻接表的顶点表结点结构为 adjvex next

边表结点EdgeNode的结构为

下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。

int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型 {

int dgree, j; EdgeNode *p;

degree= (1) ; for(j=0;jn;j++) {

p=G->adjlist［j］. firstedge; while ( (2) ) {

if( (3) ) {

degree++; break; }

p=p->next; } }

return degree; }

(1)degree=0; (2)p

(3)p->adj==vi data next

33.已知单链表的结点结构为

下列算法对带头结点的单链表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)L->next

(2)q->datadata (3)p!=min (4)p=p->next

五、算法设计题(本题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)。 typedef struct node { int x;

struct node *next; } NODE;

typedef NODE * LinkList; void adjust( LinkList header ) {

NODE *pTmp = header; //用来保存偶数链表尾指针 NODE *pCur = header->next; //链表遍历指针 NODE *pOddHdr = header->next;//奇数链表头指针 NODE *pOddTail = header->next;//奇数链表尾指针

int bIsOdd = true; //奇数结点标志，第一个结点是奇数结点

if( NULL == pCur )//空链表，不需要处理 return;

while( pCur->next != NULL )//从第二个结点开始遍历 {

pCur = pCur->next; bIsOdd = !bIsOdd;

if( bIsOdd ) //（这步错误，未将原链表的接点连接） {//奇数结点，加入奇数链表表尾 pOddTail->next = pCur; pOddTail = pCur; } else

{//偶数结点，加入偶数链表表尾 pTmp->next = pCur; pTmp = pCur; } }

pOddTail->next = NULL;//奇数链表表尾结点的next置空

pTmp->next = pOddHdr;//奇数链表插入偶数链表表尾（这步错误，未考虑最后接点的奇偶性。） return; }

全国2004年1月高等教育自学考试

数据结构试题 课程代码：02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．在数据结构中，数据的逻辑结构可以分成（ ） A．内部结构和外部结构 B．线性结构和非线性结构 C．紧凑结构和非紧揍结构 D．动态结构和静态结构

2．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ） A．数据元素的相邻地址表示 B．数据元素在表中的序号表示 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的数据域互换