(8-1)*10+(6-1)为以行序连续存放时A[8][6]え素前元素个数,((8-1)*10+(6-1))*4表示它们所占空间
第5章 数组与广义表 一、选择题(烸小题1分共10分) 1.一个向量第一个元素的存储地址是100,每个元素的长度为2则第5个元素的地址是( A )。 A.110 B.108 C.100 D.120 2.在数组A中每一个数组元素A[i][j]占用3个存储字节,行下标i从1到8列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中则存放该数组至少需要的存储字节数是( C 设有数組A[i,j],数组的每个元素长度为3字节i的值为1到8,j的值为1到10数组从内存首地址BA开始顺序存放,当用以列为主存放时元素A[5,8]的存储首地址为( B ) A. BA+141 B. BA+180 C. BA+222 D 8.设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主存储,a11为第一元素其存储地址为1,每个元素占一个地址空间则a85的地址為( B、 45 C、 36 D、 16 14.有一个100*90的稀疏矩阵,非0元素有10个设每个整型数占2字节,则用三元组表示该矩阵时所需的字节数是( B )。 A、 60 B、 66 C、 18000 D、 33 15.设二维数組A[1.. m1.. n](即m行n列)按行存储在数组B[1..m*n]中,则二维数组元素A[ij]在一维数组B中的下标为( A )。
算法中的每一条指令必须有确切嘚含义 |
线性表中的数据元素有一个前驱多个后继
用顺序结构存储,删除最后一个结点时( )
A一定不会移动其它结点位置
C可能会移动其咜结点位置
D会移动其它结点位置
1.假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许表中含有值相同的元素)排列的线性表C并要求利用原表(即A表和B表)的结点空间构造C表。
//将合并逆置后嘚结果放在C表中并删除B表
假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针已知s为指向链表中某个结点的指针,试编寫算法在链表中删除指针s所指结点的前驱结点
若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列合法的是( );
设计一个迷宫求解的算法采用___________数据结构最佳。
A线性表的顺序存储结构
D线性表的链式存储结构
1.试写一个算法识别依次读入的一个鉯@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’且序列2是序列1的逆序列。例如‘a+b&b+a’是属该模式的字符序列,而‘1+3&3-1’则不是
空串与空格串是相同的,这种说法____
A串中所含非空格字符的个数
B串中所含字符的个数
C串中所含鈈同字母的个数
D串中所含不同字符的个数
串是一种数据对象和操作都特殊的线性表。
数组A中每个元素A数组a中每个元素的长度为3B个字节,荇下标i从1到8列下标j从1到10,从首地址SA开始连续存放在存储器内存放该数组至少需要的单元数是______。
假设有二维数组A6×8每个元素用相邻的6個字节存储,存储器按字节编址已知A的起始存储位置为1000,计算数组A按行存储时元素A[14]第一个字节的位置( ) ;
A广义表的表尾总是一个广义表
B广义表难以用顺序存储结构
C 广义表的表头总是一个广义表
D广义表可以是一个多层次的结构
1.试按教科书5.5节图5.10所示的结点结构编写复制广义表的递归算法
// 由广义表L复制广义表T
假如一棵二叉树的中序遍历结果为ABCD,则结点A和结点D的关系一定不是( );
A结点A与结点D具有共同的双亲嘚右子树上的结点
B结点A是结点D的左子树上的结点
C结点A是结点D的右子树上的结点
D结点A是结点D的双亲结点
一棵哈夫曼树有17个结点则其叶子结點的个数是 _________ 。
写递归算法将二叉树中所有结点的左、右子树相互交换。
试写一个算法为一棵二叉树建立后序线索二叉树。
// 后序线索二叉树的算法
1.编写递归算法将二叉树中所有结点的左、右子树相互交换。
对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大尛为( ) ;
采用邻接表存储的图的宽度优先遍历算法类似于二叉树的( )
下面的无向带权图的最小生成树包含的边有( )
A宽度优先遍历算法
C求关键路径的方法
D深度优先遍历算法
编写算法实现从邻接表中取出某个顶点V的存储位置。
1. 对线性表进行二分查找时,要求线性表必须( )
B鉯链接方式存储,且结点按关键字有序排序
C以顺序方式存储,且结点按关键字有序排序
A右字树中所有结点的关键字大于根节点的关键字C.
B左子樹中所有结点的关键字小于根结点的关键字
C关键字插入的顺序影响二叉排序树的形态
D根结点的关键字大于左、右子树中所有结点的关键字
4.試将折半查找的算法改写成递归算法。
5.设计算法判定给定二叉树是否为二叉排序树
//last原为父节点值,但到了树叶节点后被树叶节点的key值覆蓋然后开始向上反馈key
A非终端结点中关键字的个数
B每个结点至多有m棵子树
C每个结点至少有m棵子树
1.设一组初始记录关键字序列为(50,4095,2015,7060,45)则以增量d=4 的一趟希尔排序结束后前4条记录关键字为( )。
A要排序的数据个数为奇数
B要排序的数据中含有多个相同值
C要排序的数据量呔大
D要排序的数据已基本有序
设一组初始记录关键字序列为(25,5015,3580,8520,4036,70)其中含有5个长度为2的有序子表,则用归并排序的方法對该记录关键字序列进行一趟归并后的结果为( )
1.编写算法,对n个关键字取整数值的记录序列进行整理以使所有关键字为负值的记录排在关键字为非负值的记录之前,要求:
(1)采用顺序存储结构至多使用一个记录的辅助存储空间;
(2)算法的时间复杂度为O(n);