自考数据结构试题加答案2010年

《自考数据结构试题加答案2010年》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2010年1月一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（A）A．问题规模B．语句条数C．循环层数D．函数数量2．具有线性结构的数据结构是（C）A．树B．图C．栈和队列D．广义表线性结构有：顺序表、栈和队列、串3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（C）A．O(1)B．O(m)C．O(n)D．O(m+n)4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（D）A

2、．2个B．3个C．4个D．6个P28中voidDInsertBefore(DListNode*p,DataTypex)//在带头结点的双链表中，将值为x的新结点插入结点*p之前，设p≠NULL{DListNode*s=malloc(sizeof(ListNode));①s->data=x;②s->prior=p->prior;③s->next=p;④p->prior->next=s;⑤p->prior=s;⑥}5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（D）A．3B．37C．50D．97辅导书P22中：对于循环向量

3、中的循环队列，写出通过队头队尾指针表示的队列长度公式。（front指向实际队头，rear指向实际队尾的下一元素位置。）当rear≥front时，队列长度L=rear-front；当rear

4、Full运算。7．若串str=”Software”，其子串的数目是（D）A．8B．9C．36D．37P51中：任意个连续字符组成的子序列称为该串的子串。8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为（C）A．1012B．1017C．1032D．1039P61中：在n阶方阵A这个下三角矩阵中，第i（i从0开始）行（0≤i

5、k=i(i+1)/2+j。若i

6、衡的多叉树A．B树B．AVL树AVL树是自平衡二叉查找树C．二叉排序树D．哈夫曼树哈夫曼树是最优二叉树11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（C）辅导书中P97第10题A．1，5，2，6，3，4B．1，5，6，2，3，4C．5，1，6，3，4，2D．5，1，2，6，4，312．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（D）A．v1，v2，v3，v4，v5，v6，v7B．v1，v2，v5，v4，v3，v7，v6C．v1，v2，v3，v4，v7，v5，v6D．v1，v2，v5，v6，v7，v3，v4P108P110的图7.10P114~115的图7.12

7、、图7.13、7.14深度优先遍历类似于树的前序遍历。其特点是尽可能先对纵深方向进行搜索。13．下列排序算法中不稳定的是（A）P164A．快速排序B．归并排序C．冒泡排序D．直接插入排序稳定：直接插入、冒泡、归并、基数不稳定：直接选择、希尔、快速、堆14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（B）mid1=45，mid2=9，mid3=32A．2B