数据结构key_书面作业1

一、选择题1.在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有（）个前驱结点；最后一个结点没有后继结点，其余每个结点有且只有（）个后继结点。A.1,1B.1,2C.2,1D.2,22.线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以3.指针变量p指向单链表中的结点，若该结点是链表的尾结点，下面正确的说法是()。A.p-next==NULLB.p-next!=NULLC.p==NULLD.p-next-next==NULL4.设指针p所指结点不是单链表的尾结点，删除p所指结点的后继结点的操作是（）。A.p-next=p-next-next;deletep;B.q=p-next;p-next=q-next;deletp-next;C.p-next=p-next-next;deletp-next;D.q=p-next;p-next=q-next;deleteq;5.链表不具备的特点是____。A可随机访问任何一个元素B插入、删除操作不需要移动元素C无需事先估计存储空间大小D所需存储空间与线性表长度成正比6.假定栈用单链表的存储结构表示，栈的栈顶指针为top，进行退栈时执行的操作是()。A.top-next=top;B.top=top-data;C.top=top-next;D.top-next=top-next-next;7.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____。A4，3，2，1B1，2，3，4C1，4，3，2D3，2，4，18.栈与一般线性表区别主要在方面。A元素个数B元素类型C逻辑结构D插入、删除元素的位置9.在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是。AR=F-next;BR=R-next;CF=F-next;DF=R-next;10.数据三种最主要的逻辑结构是线性结构和（）。A.线性表、树B.树形结构、图状结构C.线性表、图D.树形结构、堆二、填空题1.数据结构的存储结构包括：顺序存储表示、链式存储表示、索引存储表示和散列存储表示等四大类。2.在线性结构中，第一个结点没有前驱结点，其余每个结点有1个前驱结点；最后一个结点没有后继结点，其余每个结点有1个后继结点。3.实现字符串逆序（既输入如“ABC”，输出为“CBA”）选用栈数据结构来解决较好4.银行柜面服务遵循“先来先服务”的原则，抽号服务终端机采用队列数据结构来模拟这种行为5.线性表第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是:1086.引起循环队列（队首位置）发生变化的操作是出队7.链式队列与顺序队列相比，一个明显的优点是通常不会出现队满8.在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。如果要在第i个元素前插入一个元素，要后移n-i+1个元素。9.栈操作数据的原则是后进先出，队列操作数据的原则是先进先出。10.在栈中，可进行插入和删除操作的一端称栈顶。11.栈和队列都是_线性___结构；对于栈只能在_栈顶__插入和删除元素；对于队列只能在__队尾__插入元素和__队头__删除元素。12.计算机在运行递归程序时，要用到栈结构。13.设将整数1，2，3，4进栈，若入、出栈次序为Push,Pop,Push,Push,Pop,Pop,Push,Pop,则出栈的数字序列为1324；若想得到出栈序列1432则具体操作为：Push，Pop，Push，Push，Push，Pop，Pop，Pop14.在采用少用一个存储空间的具有n个单元的循环队列中，队满时共有n-1个元素。对于下图所示的循环队列，队满的条件是front=(rear+1)%MAXSIZE；队空的条件是rear=front三、设计题1.已知str是一个非空字符串，编写算法通过在临时栈S和队列Q中缓存数据，判处字符串str是否为回文，算法采用文字描述。①将串str分别入队Q中和入栈S中②将Q的队头元素出队至变量tq中，将S的栈顶元素出栈至变量ts中③若tq==ts，重复步骤②；若tq!=ts，则退出循环，return0表示str不是回文④return1表示str是回文2.设计函数Node*Find(Node*Head,intitem)，Head为带头结点单链表的头指针，在传入的链表中查找值为item的结点并返回其地址，如不存在这样的结点则返回空值NULL。其中结点的类型声明如下：structNode{intdata;Node*next;};Node*Find(Node*Head,intitem){Node*p=Head-next;while(p!=NULL){if(p-data==item)returnp;//查找成功p=p-next;}returnNULL;//查找失败}