数据结构期末复习题

《数据结构期末复习题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、选择或填空设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是____。l下面程序的时间复杂为（for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}）l设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为____。l设有n个待排序的记录关键字，则在堆排序中需要___

2、_个辅助记录单元。l设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为______l设关键字序列为(Kl，K2，…，Kn)，则用筛选法建初始堆必须从第______个元素开始进行筛选。l设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：ls->next=_________；2)p->next=s；3)t=p->data；4)p->data=________；5)s->data=t；l设某棵完全二叉树中有50个结点，则该二叉树中有__________

3、____个叶子结点。l下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*next;}lklist;voidlklistcreate(_____________*&head){for(i=1;i<=n;i++){p=(lklist*)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;if(i==1)head=q=p;else{q->next=p;__________;}}}l设某完全无向图中有n个顶点

4、，则该完全无向图中有____条边。l设某棵二叉树中有2000个结点，则该二叉树的最小高度为____。l设某有向图中有n个顶点，则该有向图对应的邻接表中有____个表头结点。l设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为____。l设一组初始记录关键字序列为(76，13，27，50，49，33，65，97)，则以d=4为增量的一趟希尔排序结束后的结果为_____________________________。l数据结构从逻辑上划分为三种基本类型：__________、_________和_________。l下面

5、关于线性表的叙述错误的是（A线性表采用链式存储便于插入和删除操作的实现，B线性表采用顺序存储必须占用一片连续的存储空间，C线性表采用链式存储不必占用一片连续的存储空间，D线性表采用顺序存储便于插入和删除操作的实现）。l设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有____个空指针域。l设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为____。l设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到

6、序列为____。l设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。l设散列表的长度为8，散列函数H(k)=k%7，用线性探测法解决冲突，则根据一组初始关键字序列(22，30，39，8，11，16，)构造出的散列表的平均查找长度是________。l设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为____。l设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为____。l设按照

7、从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为____。l程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的时间复杂度为____。l设带有头结点的单向循环链表的头指针变量为head，则其判空条件是____。l设某棵二叉树的高度为10，则该二叉树上叶子结点最多有____。l下列四种排序中（A.插入排序B.冒泡排序C.堆排序D.归并排序）的空间复杂度最大。l数据的最小单位是____。l设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后