数据结构作业集

第一章测试题一.简答题1:试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。答案简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。2:确定带*号语句的频度。答案对于每个y（0）值*语句执行11次，共100*11次。二.填空题1:被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系通常将数据元素间的这种联系关系称为_______答案结构2:算法的计算量的大小称为计算的_______答案复杂性三.单选题1:计算机识别.存储和加工处理的对象被统称为_______(A)数据(B)数据元素(C)数据结构(D)数据类型答案A2:程序段的时间复杂度是_______for(i=0;in;i++)for(j=1;jm;j++)A[1][j]=0;(A)0(n)(B)O(m+n+1)(C)O(m+n);(D)O(m*n)答案D3:在数据结构中，数据的逻辑结构可以分成_______(A)内部结构和外部结构(B)线性结构和非线性结构(C)紧凑结构和非紧揍结构(D)动态结构和静态结构答案B4:算法指的是_______(A)计算机程序(B)解决问题的计算方法(C)排序算法(D)解决问题的有限运算序列答案D5:若结点的存储地址与其关键字之间在某种映射关系，则称这种存储结构为_______(A)顺序存储结构(B)链式存储结构(C)索引存储结构(D)散列存储结构答案D第二章测试题—.简答题1:单链表和双向链表中，能否从当前结点出发访问到任意结点？答案在单链表中只能由当前结点访问其后的任一结点，应为没有指向其前驱结点的指针；而在双向链表中，既有指向后继结点的指针，又有指向趋结点的指针，故可以由当前结点出发访问链表中任一结点。2:描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。答案①首先结点是链表中存储线性表中的第一个数据元数的结点;②头结点:为了管理上的方便在第一个元素结点（首元结点）之前附设一个结点，该结点用来存放首元结点的地址;③头指针是指向链表中第一个结点的指针，由于有头结点，则不管线性表是否为空，头指针均不为空。3:简述线性表的两种存储结构的主要优缺点及各自适用的场合。答案线性表的两种主要存储结构各有其优点和缺点，不能简单地说哪个好哪个差要根据其适用的场合使用。顺序存储是按索引（隐含的）直接存取数据元素，方便灵活、效率髙、但插入、删除操将引起元素移动，降低了效率；链式存储采用动态分配，利用率髙，但需增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入。删除操作十分简单顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况。而链式存储适用于频繁进行元素的动态插入或删除操作的场合。二.单选题1:为了方便地在线性结构的数据中插入一个数据元素，则其数据结构宜采用_______方式。(A)顺序存储(B)链式存储(C)索引存储(D)散列存储答案B2:在双向循环链表中，在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—〉llink=p—〉llink;q—〉rlink=p;p—〉llink=q;p—〉llink=q;答案C三:填空题1:根据线性表的链式存储结构，每个结点所含指针的个数，链表分为_______和_______，而根据指针的链接方式，链表又可分为_______和_______答案单链表。多重链表。循环链表。普通链表2:在顺序表中插入或删除一个元素，需要平均移动_______元素，具体移动的元素个数与_______有关。答案n\2。插入或删除元素的位置四.判断题1:链式存储相比顺序存储的优点是插入和删除操作的时间效率高，缺点是存储密度小，不能随机查找。答案是五.问答题1:设顺序表va中的数据元素递增有序，试写一算法使x插入到顺序表的适当位置上以保证该表的有序。答案2:假设有一个单向循环链表，其结点含有三个域：pre,data和link,pre值为空指针。试编写算法将此表改为双向链表。答案3:试写出在无头结点的单链表的第i个元素之前插入一个元素的算法。答案当i=0时，则出错，无法进行插入；当i=1时，则插入的结点为首元结点。当in（n为链表中结点的个数）时，则出错，无法进行插入，当li=n时，则可以进行插入，但在搜索第i个结点时，一定要记住i的前驱结点。}4:设计实现在单链表中删除值相同的多余结点的算法。答案5:设x和y是表示单链表的两个串，试写出一个算法，找出x中第1个不在y中出现的字符（假定每个结点只存放一个字符）。答案}6:试写出一个完整的算法，以实现单链表的建立、插入、删除、逆转、输出。答案第三章测试题一.填空题1:若一个栈的输出序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是_______答案2:设有一个空栈，栈顶指针为1000H（十六进制），现有一输入序列为1，2，3，4，5，经过PUSH，PUSH,，POP，PUSH，POP，PUSH，PUSH后，输出序列是_______，栈顶指针是_______答案2，3。1003H二．单选题1:向顺序栈中压入新元素时，习惯上应当_______(A)先移动栈顶指针，再存入元素(B)先存入元素,再移动栈顶指针(C)先后次序无关紧要(D)同时进行答案B2:对于单链表形式的队列，队空的条件是_______(A)F=R=nil(B)F=R(C)F≠nil且R=nil(D)R—F=1答案B三．问答题1:试说明下述运算的结果。(1)POP(PUSH(S,A));(2)PUSH(S,POPCS));(3)PUSH'(S,POP(PUSH(S,B)))答案(1)首先要实现运算PUSH(S,A)，其结果是将元素A压入栈中。若栈S满，出现上溢现象;否则把元素A压入栈顶，且元素个数加1。然后做POP(S)运算，将栈顶元素弹出，且元素个数减1。(2)首先做POP（S）运算。若栈A为空，则做下溢处理;否则弹出栈顶元素。然后再进行压入运算，将刚才弹出的元素压入栈中。(3)在(1)、(2)的基础上，使栈S增加一个栈顶元素B。2:设一数列的顺序为1,2,3，4,5，6,通过栈操作，我们要得到顺序为3，2，5，6，4，1和1，5，4，6，2，3的输出序列，可能吗？为什么？答案输出序列3，2，5，6，4，1是可能的，但输出序列1，5，4，6，2，3不可能，因为5在4，2，3之前出栈，那么5出栈时，栈内状态为5，4，3，2，所以其次序（根据先进后出的原则）只能是5，4，3，2，而不可能出现5，4，2，3想出2时，2却被3压在下面，2不能比3先出栈，所以不可能出现1，5，4，6，2，3这种序列。3:何为队列上溢现象？何为假溢出现象？解决它有哪些方法？分别简述其工作原理。答案在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队的容量（存储空间的大小）为m。当有元素要加入队列时，若rear==ni（初始时rear=0），则发生队列的上溢现象，该元素不能加入队列。假溢出现象是队列中有空余的空间，但元素不能进队列，造成这种现象的原因是由于队列的操作方式所致。队列的上溢有以下几种方法：(1)建立一个足够大的存储空间，但这样做会造成空间利用率低。(2)当出现假溢出时，可采用以下几种方法:①采用平移元素的方法。每当队列中加入一个元素时，队列中已有的元素向队头移动一个位置（当有空余空间时）;②每当删除一个队头元素时，则依次序移队中的元素，始终使front指针指向队列中的第一个位置;③采用循环队列方式。把队头队尾看成是一个首尾相连的循环队列，虽然物理上队尾在队首之前，但逻辑上队首仍然在前，作插入和删除时仍按“先进先出”原则。4:在用一维数组sequ[0::m—1]存储循环队列的元素时，怎样设置一个标志tag来区分尾指针（rear）和头指针（front）相等时队列的状态是“空”还是“满”?答案设标志tag初始值为“0”，如果由于元素入队列使得rear-front时，则置tag为“1”;反之，如果由于元素出队列使得rear=front时，则置tag为“0”。当下一次进行入队列或出队列操作时，若有rear=front成立，则可由标志位tag的值来区别队列当前的状态是“满”还是“空”，即可决定其操作能否进行。四．判断题1:线性表采用顺序存储表示时，必须占用一片连续的存储单元，判断该说法的正误。答案是五.问答题1:用n个单元的一维数组构成一个循环队列，如何由首指针front和尾指针rear计算队列中现有元素的个数。答案2:两个栈SI和S2都采用顺序表示，并且共享一个存储区，V[1::n]。为尽量利用空间，减少溢出的可能性，现采用栈顶相对，迎面增长的方式存储。试设计公用栈的操作算法。答案3:假设以带头结点的循环链表表示队列;并且只设—个指针指向队尾结点，但不设头指针。试设计相应的置队列空，入队列和出队列的算法。答案}4:试写一个判别表达式中开.闭括号是否配对出现的算法。答案5:假设以数组sequ[0::m—1]存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。试写出此循环队列的队满条件，并设计相应的入队列和出队列的算法。答案6:设计算法以实现顺序栈的建立.入栈.出找.清空栈.查看.显示等基本操作。答案7:（选做）设有一个双端队列，元素进入该队列时的顺序为1，2，3，4。分别求出满足以下条件的输出序列：(1)能由输入受限双端队列得到,但不能由输出受限双端队列得到的输出序列；(2)能由输出受限双端队列得到，但不能由输入受限双端队列得到的输出序列；(3)既不能由输入受限双端队列得到，又不能由输出受限双端队列得到的输出序列。答案第四章测试题一.单选题1:若串S=’syntax’，其子串的数目是_______(A)6(B)21(C)22(D)7答案C二．问答题1:空串和空格串有何区别?字符串中的空格符有何意义?空串在串处理中有何作用?答案2:令s=’aaab’t=’abcaabbabcabaacbacba’。分别求出它们的next函数值。答案第五章测试题一.单选题1:有一个10阶的对称矩阵a,采用压缩存储方式：以行序为主序，a11为第一个元素,其存储地址为1，每个元素占1个地址空间，则a85的地址为_______(A)13(B)33(C)18(D)40答案B2:一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为_______(A)n*n(B)n*(n+l)/2(C)(n+1)*(n+1)/2(D)(n-1)*n/2答案B3:二维数组a的每个元素是由6个字符组成的串，行下标i的范围从0〜8，列下标j的范围从1〜10。若a按行存放，元素a[8,5]的起始地址与当a按列存放时的元素_______的起始地址一致（每个字符占一字节）。(A)a[8，5](B)a[3，10](C)a[5，8](D)a[0，9]答案B4:知广义表ls=（a（b，c，d），e），运用head和tail函数取出ls中原子b的运算是_______(A)head(head(ls))(B)tail(head(Is))(C)head(head(tail(Is)))(D)head(tail(Is))答案C5:知广义表a=((a,b,c),(d,e,f))，从a中取出原子e的运算是_______(A)(B)(C)(D)答案D6:广义表运算式tail[((a,b)