数据结构（作业集）

《数据结构（作业集）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章测试题一.简答题1:试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。答案简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。2:确定带*号语句的频度。答案对于每个y（>0）值*语句执行11次，共100*11次。二.填空题1:被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系通常将数据元素间的这种联系关系称为_______答案结构2:算法的计算量的大小称为计算的_______答案复杂性三.单

2、选题1:计算机识别.存储和加工处理的对象被统称为_______(A)数据(B)数据元素(C)数据结构(D)数据类型答案A2:程序段的时间复杂度是_______for(i=0;i

3、)计算机程序(B)解决问题的计算方法(C)排序算法(D)解决问题的有限运算序列答案D5:若结点的存储地址与其关键字之间在某种映射关系，则称这种存储结构为_______(A)顺序存储结构(B)链式存储结构(C)索引存储结构(D)散列存储结构答案D第二章测试题—.简答题1:单链表和双向链表中，能否从当前结点出发访问到任意结点？答案在单链表中只能由当前结点访问其后的任一结点，应为没有指向其前驱结点的指针；而在双向链表中，既有指向后继结点的指针，又有指向趋结点的指针，故可以由当前结点出发访问链表中任一结点。2:描述以

4、下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。答案①首先结点是链表中存储线性表中的第一个数据元数的结点;②头结点:为了管理上的方便在第一个元素结点（首元结点）之前附设一个结点，该结点用来存放首元结点的地址;③头指针是指向链表中第一个结点的指针，由于有头结点，则不管线性表是否为空，头指针均不为空。3:简述线性表的两种存储结构的主要优缺点及各自适用的场合。答案线性表的两种主要存储结构各有其优点和缺点，不能简单地说哪个好哪个差要根据其适用的场合使用。顺序存储是按索引（隐含的）直接存取数据元素，方便灵

5、活、效率髙、但插入、删除操将引起元素移动，降低了效率；链式存储采用动态分配，利用率髙，但需增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入。删除操作十分简单顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况。而链式存储适用于频繁进行元素的动态插入或删除操作的场合。二.单选题1:为了方便地在线性结构的数据中插入一个数据元素，则其数据结构宜采用_______方式。(A)顺序存储(B)链式存储(C)索引存储(D)散列存储答案B2:在双

6、向循环链表中，在p指针所指向的结点前插入一个指针q所指向的新结点其修改指针的操作是-------（双向链表的结点结构是llink,data,rlink）(A)p—〉llink=q;q—〉rlink=p;p—〉llink—〉rlink=q;q—〉llink=q;(B)p—〉llink=q;p—〉llink—〉rlink=q;q—〉rlink=p;q—〉llink=p—〉llink;(C)q—〉rlink=p;q—〉llink=p—〉llink;p—〉llink—〉rlink=q;p—〉llink=q;(D)q—

7、〉llink=p—〉llink;q—〉rlink=p;p—〉llink=q;p—〉llink=q;答案C三:填空题1:根据线性表的链式存储结构，每个结点所含指针的个数，链表分为_______和_______，而根据指针的链接方式，链表又可分为_______和_______答案单链表。多重链表。循环链表。普通链表2:在顺序表中插入或删除一个元素，需要平均移动_______元素，具体移动的元素个数与_______有关。答案n2。插入或删除元素的位置四.判断题1:链式存储相比顺序存储的优点是插入和删除操作的时间效

8、率高，缺点是存储密度小，不能随机查找。答案是五.问答题1:设顺序表va中的数据元素递增有序，试写一算法使x插入到顺序表的适当位置上以保证该表的有序。答案2:假设有一个单向循环链表，其结点含有三个域：pre,data和link,pre值为空指针。试编写算法将此表改为双向链表。答案3:试写出在无头结点的单链表的第i个元素之前插入一个元素的算法。答案当i<=0时，则出错，无法进行插入；当i=1时，则插入的