数据结构(c语言版)试题

《数据结构(c语言版)试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构考试试卷(A)课程名称:数据结构（C语言）试卷满分100分考试时间:年月日(第周星期)题号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、选择题(每项选择2分，共34分)1、在数据结构中，与所使用的计算机无关的是（D）。A、存储结构B、物理结构C、物理和存储结构D、逻辑结构2、可以把数据的逻辑结构划分成（D）。A、内部结构和外部结构B、动态结构和静态结构C、紧凑结构和非紧凑结构D、线性结构和非线性结构3、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。A、110B、108C、100D、1204、栈

2、结构通常采用的两种存储结构是（A）。A、顺序存储结构和链式存储结构；B、散列方式和索引方式；C、链式存储结构和数组；D、线性存储结构和非线性存储结构。5、在下列链表中不能从当前结点出发访问到其余各结点的是（A）。A、单链表B、单循环链表C、双向链表D、双向循环链表学院：专业：学号：姓名：装订线广东工业大学试卷用纸，共6页，第10页6、在表长为n的单链表中，算法时间复杂度为O(n)的操作是（A）。A、查找单链表中第i个结点。B、在当前结点之后插入一个结点。C、删除表中第一个结点。D、删除当前结点的直接后继结点。7、数组A中，每个数据元素的长度为3个字节，行

3、下标从1到8，列下标从3到10，存放该数组至少需要的单元数是（D）。A、80B、100C、240D、2708、稀疏矩阵一般的压缩存储方法有两种，即（C）。A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表9、广义表（a,b,c,d）的表头是（A）表尾是（D）。A、aB、bC、(a,b)D、(b,c,d)10、已知二叉树的后序序列为fgbedca，中序序列为fbgadec则该二叉树的前序序列为（B），层次序列为（C）。A、abcdefgB、abfgcdeC、abcfgdeD、fgedcba11、某二叉树只有度为0和度为2的结点，如

4、果该二叉树只有21个结点，则叶子结点数为（C）。A、9B、10C、11D、1212、一个有n个顶点的无向图最多有（C）条边。A、nB、n(n-1)C、n(n-1)/2D、2n13、对于一个具有n个顶点e条边的无向图，若采用邻接矩阵表示，该矩阵大小是（D）。A、e2B、n+eC、n*eD、n214、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（A）方法。A、分块B、顺序C、二分D、散列广东工业大学试卷用纸，共6页，第10页15、在以下排序算法中，关键字的比较次数与记录的初始排列次序无关的是（D）。A、希尔排序B、起泡排序C、插入排序D

5、、选择排序二、算法测试（共28分）先按要求填空完成程序，再回答有关问题。1、（31分）设h是带表头结点的单链表的头指针，请设计一个逆置这个单链表的程序。即原链表为(a1,a2,a3…an)，逆置后变为(an,an-1…a2,a1)。单链表结点结构为：typedefstructnode{intdata;___structnode*link;__（2分）}LNode;voidinvert(LNode*h){LNode*s,*p;p=h->link;h->link=___NULL；或者0；（2分）while(p!=NULL){s=p;p=p->link;__s

6、->link=h->link;_（2分）h->link=s;}}什么是表头结点？（2分）如果该链表无表头结点，则原程序该做怎样的修改？（4分）广东工业大学试卷用纸，共6页，第10页1、（13分）对以下函数填空，实现以带头结点的单链表h为存储结构的直接选择排序。单链表的结点结构定义为typedefstructnode{intkey;structnode*next;}JD;voidzjxzpx(JD*h){JD*p,*q,*m;intx;p=h->next;while(p!=NULL){q=p->next;m=p;while(q!=NULL){if(m->k

7、ey>q->key)_________;（2分）_____________;（2分）}if(p!=m){x=p->key;p->key=m->key;m->key=x;}______________;（2分）}直接选择排序属于___________(稳定/不稳定)排序。（2分）该排序算法总的键值比较次数为____________。（2分）并分析什么情况下有最小移动记录次数？什么情况下有最大移动记录次数？算法的平均时间复杂度为多少？（3分）广东工业大学试卷用纸，共6页，第10页3、（6分）对以下函数填空实现求中序线索二叉树中结点后继的算法。中序线索树中结点

8、结构定义为：typedefstructTbTree{intdata;struct