发布时间 : 星期三 文章自考数据结构历年试题及答案更新完毕开始阅读7e7bb987e53a580216fcfe68
(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;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->data
五、算法设计题(本题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的数据域互换