C.强连通图 D.有向无环图
12.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( d ) A.O(1) B.O(logn) C.O(n) D.O(n logn)
13.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( n/2 )
A. B. C. D.n
14.对于哈希函数H(key)=key,被称为同义词的关键字是( d ) A.35和41 B.23和39 C.15和44 D.25和51 15.稠密索引是在索引表中( )
A.为每个记录建立一个索引项 B.为每个页块建立一个索引项 C.为每组记录建立一个索引项 D.为每个字段建立一个索引项 二、填空题（每小题2分，若有两个空格，每个空格1分，共20分）
16.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的__(_时间复杂度_)____。
17.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作_(存储密度)_______。 date next
18.已知链栈的结点结构为 栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为________和________。
19.空串的长度是___0_____；空格串的长度是____(空格的数目_)___。
20.假设一个6阶的下三角矩阵B按列优先顺序压缩存储在一维数组A中，其中A［0］存储矩阵的第一个元素b11,则A［14］存储的元素是______b63__。
21.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是____2____。
22.如图所示的有向无环图可以排出________种不同的拓扑序列。
23.利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(___75,66,48,29,31,37_____)。
24.对长度为20的有序表进行二分查找的判定树的高度为___5_____。
25.在多重表文件中，次关键字索引的组织方式是将________的记录链接成一个链表。 26.对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。
date next
单链表和单循环链表的结点结构为 prior date next 双向链表的结点结构为
(1)单链表: (不可以,无法找到前驱接点)
(2)单循环链表(可以:q=p->next;while(q->next!=p)q=q->next;q->data<->p->data;
(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的数据域互换
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库自考数据结构历年试题及答案(4)在线全文阅读。
相关推荐：