资源描述：
《数据结构单元测验2(包含答案与讲解)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《数据结构》小测验二（2008-2009学年第一学期》一.判断题（用x表示错，用丁表示对）（每题1分，共10分）1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（X）错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。2•在表结构中最常用的是线性表，栈和队列不太常用。（X）错，不一定吧？调用子程序或函数常用，CPU中也用队列。3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（V）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性
2、表。（V）•正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而己。5.栈和链表是两种不同的数据结构。（X）错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。6.栈和队列是种非线性数据结构。（X）错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。7.栈和队列的存储方式既可是顺序方式，也可是链接方式。（J）8•两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（丿）9•队是一种插入与删除操作分别
3、在表的两端进行的线性表，是一种先进后出型结构。错，后半句不对。（X）10.—个栈的输入序列是12345,则栈的输出序列不可能是12345。（X）错，有可能。二.选择题（每项选择1分，共26分）12345BCBAD6:A:a2,B:a4,C:al,D:a2,E:27.A=2,B=2,C=1,D=6,E=48.A=2,B=1,C=2,D=4,E=391011121314CDADDD三、填空题（每空2分，共30分）1•向量、栈和队列都是线性结构,可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插
4、入和队首删除元素。1.栈是一种特殊的线性表，允许插入和删除运算的一端称为埋页。不允许插入和删除运算的一端称为栈底。2.队列是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。3.在一个循坏队列中，队首指针指向队首元素的前一个位置。4.在具有n个单元的循环队列中，队满时共有n・l个元素。5.向栈中压入元素的操作是先移动栈顶指针,后存入元素□6.从循环队列中删除一个元素吋，其操作是先一移动队首指针,后取出元素。7.带表头结点的空循环双向链表的长度等于0。L=head头结点R=headhead四.算法理解.阅读下
5、面的程序，根据写出正确的运行结果。(每题6分，共18分)得分1.不能。因为3,2出栈之前需4先出栈。2.本程序段查找栈S中有无整数为k的元素，如有，则删除。采用的办法使用另一个栈T。在S栈元素退栈时，若退栈元素不是整数k,则压入T栈。遇整数k,k不入T栈，然后将T栈元素全部退栈，并依次压入栈S中，实现了在S中删除整数k的目的。若S中无整数k,则在S退成空栈后，再将T栈元素退栈，并依次压入S栈。直至T栈空。这后一种情况下S栈内容操作前后不变。3.(1)a[订或a[l](2)a[i](3)pop(s)或s[l]；五.应用题(每题8
6、分，共16分)1.[题目分析]表达式中的括号有以下三对：'(’、')'、'['、']'、'{'、,使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对，否则,结论表达式括号不配对。intMatch(LinkedListla)//算术表达式存储在以b为头结点的单循环链表中，本算法判断括号是否正确配对{chars[];p=la->link;Stacklnit(s);while(p!=la){switch(p->ch)//s为字符栈
7、，容量足够大//p为工作指针，指向待处理结点//初始化栈S〃循环到头结点为止{case'(‘:push(s,p->ch);break;case':if(StackEmpty(s)
8、
9、StackGetTop(s)!='(‘){printf(“括号不配对”);return(0);}，［‘:push(s,p->ch);break;，］':if(StackEmpty(s)
10、
11、StackGetTop(s)!=，［‘{printf(“括号不配对");return(0);}'{':push(s,p->ch);break;"}':if
12、(StackEmpty(s)
13、StackGetTop(s)!="{'{printf(a括号不配对”);return(0);}}p=p->link;后移指针}//wh订eif(StackEmpty(s)){printf(“括号配对”);return(1);}else{p
